给定一个二叉树，返回它的 后序 遍历。
示例:
1
2
3
4
5
6
7
8
| 输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
|
方法一：递归
思路与算法
按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
定义 dfs(root) 表示当前遍历到 root 节点的答案。按照定义，我们只要递归调用 dfs(root->left) 来遍历 root 节点的左子树，然后递归调用 dfs(root->right) 来遍历 root 节点的右子树，最后将 root 节点的值加入答案即可，递归终止的条件为碰到空节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Solution2 {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.addLast(root);
root = root.left;
}
root = stack.pollLast();
if (root.right == null || root.right == pre) {
ans.add(root.val);
pre = root;
root = null;
} else {
stack.addLast(root);
root = root.right;
}
}
return ans;
}
}
|
复杂度分析
时间复杂度：O(n)，其中 nn 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。
方法二：迭代
思路与算法
可以用迭代的方式实现方法一的递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，具体可以参考下面的代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class Solution2 {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.addLast(root);
root = root.left;
}
root = stack.pollLast();
assert root != null;
if (root.right == null || root.right == pre) {
ans.add(root.val);
pre = root;
root = null;
} else {
stack.addLast(root);
root = root.right;
}
}
return ans;
}
}
|
复杂度分析
时间复杂度：O(n)，其中 nn 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。
方法三：Morris 遍历
思路与算法
可以在线性时间内，只占用常数空间来实现后序遍历。
Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其后序遍历规则总结如下：
- 新建临时节点，令该节点为 root；
- 如果当前节点的左子节点为空，则遍历当前节点的右子节点；
- 如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点；
- 如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点，当前节点更新为当前节点的左子节点。
- 如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。倒序输出从当前节点的左子节点到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右子节点。
- 重复步骤 2 和步骤 3，直到遍历结束。
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
TreeNode p1 = root, p2 = null;
while (p1 != null) {
p2 = p1.left;
if (p2 != null) {
while (p2.right != null && p2.right != p1) {
p2 = p2.right;
}
if (p2.right == null) {
p2.right = p1;
p1 = p1.left;
continue;
} else {
p2.right = null;
addPath(res, p1.left);
}
}
p1 = p1.right;
}
addPath(res, root);
return res;
}
public void addPath(List<Integer> res, TreeNode node) {
int count = 0;
while (node != null) {
++count;
res.add(node.val);
node = node.right;
}
int left = res.size() - count, right = res.size() - 1;
while (left < right) {
int temp = res.get(left);
res.set(left, res.get(right));
res.set(right, temp);
left++;
right--;
}
}
}
|
复杂度分析
时间复杂度：O(n)，其中 n 是二叉树的节点数。没有左子树的节点只被访问一次，有左子树的节点被访问两次。
空间复杂度：O(1)。只操作已经存在的指针（树的空闲指针），因此只需要常数的额外空间。