LeetCode145 二叉树的后序遍历（究极写法）

发表于 | 分类于 |
字数统计: 551 | 阅读时长 ≈ 2

链接: 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;
}