LeetCode145 二叉树的后序遍历(究极写法)

链接: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/

题意

给定一个二叉树的根节点 root ,返回它的 后序 遍历。

解法

同样学习一手后序遍历的非递归写法
使用到的第一种解法是利用前序遍历的反向写法
先将左子树入栈 再将右子树入栈
最后将结果反转就是后序遍历序列

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {

vector<TreeNode*> stk;
vector<int> ret;
if(!root) return ret;
stk.push_back(root);
while(stk.size()) {
TreeNode* top = stk.back();
ret.push_back(top -> val);
stk.pop_back();
if (top -> left) {
stk.push_back(top -> left);
}
if (top -> right) {
stk.push_back(top -> right);
}
}
reverse(ret.begin(), ret.end());
return ret;

}
};

统一版

在看题解的时候,看到一个很妙的解法,将三种不同的遍历方式进行统一
访问到节点的时候将一个nullptr入栈作为标记
利用一个nullptr节点判断当前节点是否被访问过
访问过就会在下次遇到nullptr的时候进行输出
前中后遍历统一版迭代写法(只用移动左中右的顺序即可)

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> preorderTraversal(TreeNode* root) {
if(!root) return {};
vector<int> result;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()){
TreeNode* node = stk.top();
stk.pop();
if(node){
if(node -> right){
stk.push(node -> right);
}
if(node -> left){
stk.push(node -> left);
}
stk.push(node);
stk.push(nullptr);
}else{
result.push_back(stk.top()->val);
stk.pop();
}
}
return result;
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> inorderTraversal(TreeNode* root) {
if(!root) return {};
vector<int> result;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()){
TreeNode* node = stk.top();
stk.pop();
if(node){
if(node -> right){
stk.push(node -> right);
}
stk.push(node);
stk.push(nullptr);
if(node -> left){
stk.push(node -> left);
}
}else{
result.push_back(stk.top()->val);
stk.pop();
}
}
return result;
}

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> postorderTraversal(TreeNode* root) {
if(!root) return {};
vector<int> result;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()){
TreeNode* node = stk.top();
stk.pop();
if(node){
stk.push(node);
stk.push(nullptr);
if(node -> right){
stk.push(node -> right);
}
if(node -> left){
stk.push(node -> left);
}
}else{
result.push_back(stk.top()->val);
stk.pop();
}
}
return result;
}