给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
**输入：** root = [1,null,2,3]
**输出：** [3,2,1]
示例 2：
**输入：** root = []
**输出：** []
示例 3：
**输入：** root = [1]
**输出：** [1]
提示：
- 树中节点的数目在范围
[0, 100] 内
-100 <= Node.val <= 100
进阶： 递归算法很简单，你可以通过迭代算法完成吗？
方法一：递归
思路与算法
首先我们需要了解什么是二叉树的后序遍历：按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
定义 postorder(root) 表示当前遍历到 root 节点的答案。按照定义，我们只要递归调用 postorder(root->left) 来遍历 root 节点的左子树，然后递归调用 postorder(root->right) 来遍历 root 节点的右子树，最后将 root 节点的值加入答案即可，递归终止的条件为碰到空节点。
代码
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
void postorder(TreeNode *root, vector<int> &res) {
if (root == nullptr) {
return;
}
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
postorder(root, res);
return res;
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
postorder(root, res);
return res;
}
public void postorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
postorder(root.left, res);
postorder(root.right, res);
res.add(root.val);
}
}
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
def postorder(root: TreeNode):
if not root:
return
postorder(root.left)
postorder(root.right)
res.append(root.val)
res = list()
postorder(root)
return res
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
| func postorderTraversal(root *TreeNode) (res []int) {
var postorder func(*TreeNode)
postorder = func(node *TreeNode) {
if node == nil {
return
}
postorder(node.Left)
postorder(node.Right)
res = append(res, node.Val)
}
postorder(root)
return
}
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void postorder(struct TreeNode *root, int *res, int *resSize) {
if (root == NULL) {
return;
}
postorder(root->left, res, resSize);
postorder(root->right, res, resSize);
res[(*resSize)++] = root->val;
}
int *postorderTraversal(struct TreeNode *root, int *returnSize) {
int *res = malloc(sizeof(int) * 2001);
*returnSize = 0;
postorder(root, res, returnSize);
return res;
}
|
复杂度分析
方法二：迭代
思路与算法
我们也可以用迭代的方式实现方法一的递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，具体可以参考下面的代码。
<,,,,,,,,,,,,,,,,,,>
代码
[sol2-C++]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
| class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
if (root == nullptr) {
return res;
}
stack<TreeNode *> stk;
TreeNode *prev = nullptr;
while (root != nullptr || !stk.empty()) {
while (root != nullptr) {
stk.emplace(root);
root = root->left;
}
root = stk.top();
stk.pop();
if (root->right == nullptr || root->right == prev) {
res.emplace_back(root->val);
prev = root;
root = nullptr;
} else {
stk.emplace(root);
root = root->right;
}
}
return res;
}
};
|
[sol2-Java]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
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == prev) {
res.add(root.val);
prev = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return res;
}
}
|
[sol2-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return list()
res = list()
stack = list()
prev = None
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if not root.right or root.right == prev:
res.append(root.val)
prev = root
root = None
else:
stack.append(root)
root = root.right
return res
|
[sol2-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func postorderTraversal(root *TreeNode) (res []int) {
stk := []*TreeNode{}
var prev *TreeNode
for root != nil || len(stk) > 0 {
for root != nil {
stk = append(stk, root)
root = root.Left
}
root = stk[len(stk)-1]
stk = stk[:len(stk)-1]
if root.Right == nil || root.Right == prev {
res = append(res, root.Val)
prev = root
root = nil
} else {
stk = append(stk, root)
root = root.Right
}
}
return
}
|
[sol2-C]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
| int *postorderTraversal(struct TreeNode *root, int *returnSize) {
int *res = malloc(sizeof(int) * 2001);
*returnSize = 0;
if (root == NULL) {
return res;
}
struct TreeNode **stk = malloc(sizeof(struct TreeNode *) * 2001);
int top = 0;
struct TreeNode *prev = NULL;
while (root != NULL || top > 0) {
while (root != NULL) {
stk[top++] = root;
root = root->left;
}
root = stk[--top];
if (root->right == NULL || root->right == prev) {
res[(*returnSize)++] = root->val;
prev = root;
root = NULL;
} else {
stk[top++] = root;
root = root->right;
}
}
return res;
}
|
复杂度分析
方法三：Morris 遍历
思路与算法
有一种巧妙的方法可以在线性时间内，只占用常数空间来实现后序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。
Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其后序遍历规则总结如下：
新建临时节点，令该节点为 root；
如果当前节点的左子节点为空，则遍历当前节点的右子节点；
如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点；
重复步骤 2 和步骤 3，直到遍历结束。
这样我们利用 Morris 遍历的方法，后序遍历该二叉搜索树，即可实现线性时间与常数空间的遍历。
代码
[sol3-C++]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
| class Solution {
public:
void addPath(vector<int> &vec, TreeNode *node) {
int count = 0;
while (node != nullptr) {
++count;
vec.emplace_back(node->val);
node = node->right;
}
reverse(vec.end() - count, vec.end());
}
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
if (root == nullptr) {
return res;
}
TreeNode *p1 = root, *p2 = nullptr;
while (p1 != nullptr) {
p2 = p1->left;
if (p2 != nullptr) {
while (p2->right != nullptr && p2->right != p1) {
p2 = p2->right;
}
if (p2->right == nullptr) {
p2->right = p1;
p1 = p1->left;
continue;
} else {
p2->right = nullptr;
addPath(res, p1->left);
}
}
p1 = p1->right;
}
addPath(res, root);
return res;
}
};
|
[sol3-Java]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--;
}
}
}
|
[sol3-Python3]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
| class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
def addPath(node: TreeNode):
count = 0
while node:
count += 1
res.append(node.val)
node = node.right
i, j = len(res) - count, len(res) - 1
while i < j:
res[i], res[j] = res[j], res[i]
i += 1
j -= 1
if not root:
return list()
res = list()
p1 = root
while p1:
p2 = p1.left
if p2:
while p2.right and p2.right != p1:
p2 = p2.right
if not p2.right:
p2.right = p1
p1 = p1.left
continue
else:
p2.right = None
addPath(p1.left)
p1 = p1.right
addPath(root)
return res
|
[sol3-Golang]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
| func reverse(a []int) {
for i, n := 0, len(a); i < n/2; i++ {
a[i], a[n-1-i] = a[n-1-i], a[i]
}
}
func postorderTraversal(root *TreeNode) (res []int) {
addPath := func(node *TreeNode) {
resSize := len(res)
for ; node != nil; node = node.Right {
res = append(res, node.Val)
}
reverse(res[resSize:])
}
p1 := root
for p1 != nil {
if p2 := p1.Left; p2 != nil {
for p2.Right != nil && p2.Right != p1 {
p2 = p2.Right
}
if p2.Right == nil {
p2.Right = p1
p1 = p1.Left
continue
}
p2.Right = nil
addPath(p1.Left)
}
p1 = p1.Right
}
addPath(root)
return
}
|
[sol3-C]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
| void addPath(int *vec, int *vecSize, struct TreeNode *node) {
int count = 0;
while (node != NULL) {
++count;
vec[(*vecSize)++] = node->val;
node = node->right;
}
for (int i = (*vecSize) - count, j = (*vecSize) - 1; i < j; ++i, --j) {
int t = vec[i];
vec[i] = vec[j];
vec[j] = t;
}
}
int *postorderTraversal(struct TreeNode *root, int *returnSize) {
int *res = malloc(sizeof(int) * 2001);
*returnSize = 0;
if (root == NULL) {
return res;
}
struct 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, returnSize, p1->left);
}
}
p1 = p1->right;
}
addPath(res, returnSize, root);
return res;
}
|
复杂度分析
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
>