NO.94 中序 中等 NO.144 前序 中等 NO.145 后序 困难
这三种遍历有一个共同特点:都是深搜的一种形式。
思路一:迭代实现
以中序遍历为例,实现之后,对于前序和后序就是调整节点访问顺序即可。
不断地向左节点深搜,借助栈结构,将当前节点入栈。直至左节点为空,弹出栈顶节点,保存节点值,并将弹出的节点不断向左节点深搜并保存每个节点。。。
中序遍历
1 | public List<Integer> inorderTraversal(TreeNode root) { |
前序遍历
1 | public List<Integer> preorderTraversal(TreeNode root) { |
后序遍历
后序遍历的迭代实现稍有不同。记录两个较为朴素通用的方法:
转换问题,将后序遍历的左右根的顺序,看作是根右左的翻转。根右左从哪里来?前序遍历的根左右,调整左右的压栈顺序即可得到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
if (root != null) {
stack.push(root);
res.add(root.val);//根
root = root.right;//右
} else {
TreeNode pop = stack.pop();
root = pop.left;//左
}
}
//得到根右左的序列,翻转得到后序遍历的左右根
Stack<Integer> s = new Stack<>();
for (Integer e : res) s.push(e);
res.clear();
while (!s.isEmpty()) res.add(s.pop());
return res;
}依然采用栈来模拟,但是比前序和中序要麻烦一些。比如中序遍历,当左子树遍历完毕,可以将根弹出然后去遍历右子树即可。
但是后序遍历中左子树遍历完毕,不能立刻将根pop而是peek出根,然后去遍历右子树,只有当右子树也遍历完毕才能弹出根。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
//用set记录访问过的节点
Set<TreeNode> set = new HashSet<>();
TreeNode cur = root;
while (!stack.isEmpty() || root != null) {
//节点不为空且没有被访问过,入栈
while (cur != null && !set.contains(cur)) {
stack.push(cur);
cur = cur.left;//左
}
//遍历完左子树,peek根节点
cur = stack.peek();
//如果cur的右子树为空,或者第二次访问节点
if (cur.right == null || set.contains(cur)) {
//记录根节点,并弹出
res.add(cur.val);
set.add(cur);
stack.pop();
//如果栈不空,继续检查遍历下一个栈顶元素的右子树
if (stack.isEmpty()) return res;
cur = stack.peek().right;
} else {//右子树不为空并且第一次访问,遍历右子树
set.add(cur);
cur = cur.right;//右
}
}
return res;
}
思路二:递归实现
递归的思路是借助递归栈。
中序遍历
1 | List<Integer> res = new ArrayList<>(); |
前序遍历
1 | List<Integer> res = new ArrayList<>(); |
后序遍历
1 | List<Integer> res = new ArrayList<>(); |
ps:都是完成一次遍历,时间复杂度O(n),空间上取决于树的高度(深度)。
本人菜鸟,有错误请告知,感激不尽!
更多题解和源码:github