欢迎访问LeetCode题解合集

题目描述

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

题解：

后序遍历：左子树 右子树 根节点。

又是帮忙复习各种各样写法的。

法一：

递归。

时间复杂度：$O(n)$

额外空间复杂度：$O(n)$

class Solution {
public:
    vector<int> ret;
    void dfs( TreeNode *root ) {
        if ( !root ) return;
        dfs( root->left );
        dfs( root->right );
        ret.emplace_back( root->val );
    }
    vector<int> postorderTraversal(TreeNode* root) {
        dfs( root );
        return ret;
    }
};
/*
时间：0ms，击败：100.00%
内存：8.3MB，击败：62.93%
*/

法二：

迭代。

时间复杂度：$O(n)$

额外空间复杂度：$O(n)$

其中 prev 记录右子树被访问的最后一个节点，只有当右子树被访问过，才能保存根节点的值。

class Solution {
public:
    vector<int> ret;
    vector<int> postorderTraversal(TreeNode* root) {
        if ( !root ) return {};
        stack<TreeNode*> stk;
        TreeNode *prev = nullptr;
        while ( root || stk.size() ) {
            while ( root ) {
                stk.emplace( root );
                root = root->left;
            }
            root = stk.top();
            if ( !root->right || root->right == prev ) {
                ret.emplace_back( root->val );
                prev = root;
                stk.pop();
                root = nullptr;
            } else root = root->right;
        }
        return ret;
    }
};
/*
时间：0ms，击败：100.00%
内存：8.1MB，击败：87.16%
*/