跳转至

145.二叉树的后序遍历 (Hard)*

题目描述*

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

示例*

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

   1
    \
     2
    /
   3

输出: [3,2,1]

进阶*

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

代码*

递归还是很简单。

迭代有几种方法：

  1. 与前序遍历相似的方法进行遍历，每到一结点 A，立即访问它，然后将左子树入栈，再次遍历右子树。最后结果再逆序即得到后序遍历序列。
  2. 每到一个结点 A，根要最后访问，将其入栈，然后遍历左子树，遍历右子树，最后返回到 A。问题是无法区分从左子树返回还是从右子树返回，使用辅助标记。
  3. 记录上一次遍历的结点，比较是否等于右结点即可。
class Solution {
public:
    void helper(TreeNode *root, vector<int>& res) {
        if(root != nullptr) {
            helper(root->left, res);
            helper(root->right, res);
            res.push_back(root->val);
        }
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        helper(root, res);
        return res;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> helpStack;
        TreeNode *cur = root;
        while(cur != nullptr || !helpStack.empty()) {
            while(cur != nullptr) {
                res.push_back(cur->val);
                helpStack.push(cur->left);
                cur = cur->right;
            }
            cur = helpStack.top();
            helpStack.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> helpStack;
        unordered_map<TreeNode*, int> isRight;
        TreeNode *cur = root;
        while(cur != nullptr || !helpStack.empty()) {
            while(cur != nullptr) {
                helpStack.push(cur);
                cur = cur->left;
            }
            while(!helpStack.empty() && isRight[helpStack.top()]) {
                res.push_back(helpStack.top()->val);
                helpStack.pop();
            }
            if(!helpStack.empty()) {
                cur = helpStack.top()->right;
                isRight[helpStack.top()] = 1;
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> helpStack;
        TreeNode *cur = root, *last = nullptr;
        while(cur != nullptr || !helpStack.empty()) {
            while(cur != nullptr) {
                helpStack.push(cur);
                cur = cur->left;
            }
            TreeNode *tmp = helpStack.top();
            if(tmp->right != nullptr && tmp->right != last) {
                cur = tmp->right;
            }else {
                res.push_back(tmp->val);
                last = tmp;
                helpStack.pop();
            }
        }
        return res;
    }
};
最后更新: July 23, 2022