题目
(https://leetcode.com/problems/binary-tree-inorder-traversal/)
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
分析
image.png
参考一篇感觉写的比较好的
(https://www.cnblogs.com/llguanli/p/7363657.html)
代码
递归代码
class Solution {
class Solution {
List<Integer> results= new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if(null!=root){
//遍历左子树
inorderTraversal(root.left);
results.add(root.val);
//遍历右子树
inorderTraversal(root.right);
}
return results;
}
}
非递归
class Solution {
LinkedList<TreeNode> stack = new LinkedList<>();
List<Integer> results = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode pNode = root;
while (pNode != null || !stack.isEmpty()) {
if (pNode != null) {
stack.push(pNode);
pNode = pNode.left;
} else { //pNode == null && !stack.isEmpty()
TreeNode node = stack.pop();
results.add(node.val);
pNode = node.right;
}
}
return results;
}
}
结果
递归结果
image.png
非递归结果
zuo
