题目链接：Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
这道题的要求是后序遍历二叉树。
二叉树，即每个节点下面最多有2个子节点的树。
-
递归遍历
递归遍历二叉树，比较简单。
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
public:
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> vi;
postorderTraversal(root, vi);
return vi;
}
private:
void postorderTraversal(TreeNode *root, vector<int> &vi)
{
if(root != NULL)
{
postorderTraversal(root -> left, vi);
postorderTraversal(root -> right, vi);
vi.push_back(root -> val);
}
}
};
-
迭代遍历1
用栈进行存储，根节点先入栈。然后不断读取栈顶元素并弹栈，读取某一节点的时候，如果存在左子树，左子节点入栈，并将left指针标记为NULL。如果存在右子树，右子节点入栈，并将right指针标记为NULL。如果左右子树均不存在，说明没有左右子树或者已经遍历完左右子树了，因此记录该节点并弹栈。这样，直到栈为空。
该方法缺点，破坏了原二叉树的结构。
时间复杂度：O(n)
空间复杂度：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
25
26
27
28
29
30
31
32
33
34
35
class Solution
{
public:
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> vi;
if(root == NULL)
return vi;
stack<TreeNode *> stp;
stp.push(root);
while(!stp.empty())
{
TreeNode *p = stp.top();
if(p -> left != NULL)
{
stp.push(p -> left);
p -> left = NULL;
}
else if(p -> right != NULL)
{
stp.push(p -> right);
p -> right = NULL;
}
else
{
stp.pop();
vi.push_back(p -> val);
}
}
return vi;
}
};
-
迭代遍历2
由于上面方法破坏了原有二叉树的结构，并不是很好。其实后序遍历的重点就是标记出何时左右子树都访问完，这样才能访问当前节点。采用pre指针指向前一节点，这样，再弹出节点时，通过pre的状态和左右子树就能发现是否访问完左右子树：
- 如果左右子树均为NULL，说明根本就没有左右子树，因此可以访问当前节点；
- 如果右子树不为NULL，并且pre等于右子节点，说明已经访问完右子树，也就是说已经访问完左右子树了，因此可以访问当前节点；
- 如果右子树不NULL，并且pre等于左子节点，说明已经访问完左子树，而且右子树不存在，因此可以访问当前节点。
而当可以访问当前节点的时候，记录当前节点并弹栈，同时将pre指向当前节点。
接下来，如果存在右子树，说明需要后遍历右子树，因此右子节点先入栈。如果存在左子树，左子节点入栈。
就这样，直到栈为空。
时间复杂度：O(n)
空间复杂度：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
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution
{
public:
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> vi;
if(root == NULL)
return vi;
TreeNode *pre = NULL;
stack<TreeNode *> stp;
stp.push(root);
while(!stp.empty())
{
TreeNode *p = stp.top();
if( p -> left == NULL && p -> right == NULL ||
p -> right != NULL && p -> right == pre ||
p -> right == NULL && p -> left == pre)
{
stp.pop();
vi.push_back(p -> val);
pre = p;
continue;
}
if(p -> right != NULL)
stp.push(p -> right);
if(p -> left != NULL)
stp.push(p -> left);
}
return vi;
}
};
-
迭代遍历3
注意一下前序遍历，顺序是p、p->left、p->right，而后序遍历，顺序是p->left、p->right、p。因此，可以先采用如下遍历顺序：p、p->right、p->left（代码和前序遍历及其类似），然后将其反转，就为后序遍历。
时间复杂度：O(n)
空间复杂度：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
25
26
27
28
class Solution
{
public:
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> vi;
if(root == NULL)
return vi;
stack<TreeNode *> stp;
stp.push(root);
while(!stp.empty())
{
TreeNode *p = stp.top();
vi.push_back(p -> val);
stp.pop();
if(p -> left != NULL)
stp.push(p -> left);
if(p -> right != NULL)
stp.push(p -> right);
}
reverse(vi.begin(), vi.end());
return vi;
}
};
-
Morris Traversal方法1
该方法只需要O(1)空间，而且同样可以在O(n)时间内完成遍历二叉树。
注意一下前序遍历，顺序是p、p->left、p->right，而后序遍历，顺序是p->left、p->right、p。因此，可以先采用Morris Traversal方法实现如下遍历顺序：p、p->right、p->left（代码和前序遍历及其类似），然后将其反转，就为后序遍历。
其实就是将Morris Traversal方法的前序中的left换为right，right换为left就可以实现p、p->right、p->left的顺序。
时间复杂度：O(n)
空间复杂度：O(1)
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
class Solution
{
public:
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> vi;
TreeNode *cur = root, *pre = NULL;
while(cur != NULL)
{
if(cur -> right == NULL)
{
vi.push_back(cur -> val);
cur = cur -> left;
}
else
{
pre = cur -> right;
while(pre -> left != NULL && pre -> left != cur)
pre = pre -> left;
if(pre -> left == NULL)
{
pre -> left = cur;
vi.push_back(cur -> val);
cur = cur -> right;
}
else
{
pre -> left = NULL;
cur = cur -> left;
}
}
}
reverse(vi.begin(), vi.end());
return vi;
}
};
详见这里。
-
Morris Traversal方法2
该方法只需要O(1)空间，而且同样可以在O(n)时间内完成遍历二叉树。
详见这里。