1.题目描述
示例:
1
2
3
4
5
6
7
8
9 > 输入: [1,null,2,3]
> 1
> \
> 2
> /
> 3
> 输出: [1,3,2]
> 进阶: 递归算法很简单,你可以通过迭代算法完成吗?
>
2.解题思路
思路1:使用递归
中序遍历的 左子树--> 跟--> 右子树
思路2:迭代
用一个指针模拟访问过程,先遍历到root的最左节点,
1
2
3
4
5
6
7
8
9
10
11
12 > 1
> / \
> 2 3
> / \ /
> 4 5 6
> (1)第一次循环,栈stack里面放入root的左子树:分别放入1--2--4为root的树,然后ans里面存入stack.pop(),即4,cur = cur.right = null
> (2)stack内有2个TreeNode,进入第二次循环,ans.add(cur.val) = 2;cur = cur.right = 5;
> (3)stack里面还有一个以1为root的TreeNode,进入第三次循环,stack加入以5为root的TreeNode,ans加入5,cur = null,
> (4)stack里面还有一个以1为root的TreeNode,进入第四次循环,ans加入1,cur = cur.right = 3
> (5)cur!=null,进入第四次循环,stack加入3和6为root的树,ans加入6,cur = null
> (6) stack里面还有一个以3为root的TreeNode,进入第五次循环,ans加入3,cur = null,stack为空,结束循环
>
3.代码
方法1:递归
1 | /** |
方法2:迭代
1 | public static List<Integer> inorderTraversal2(TreeNode root) { |