题解 | #二叉树的后序遍历#

class Solution {
  public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans, reverse;
        if(root == NULL){
            return ans;
        }
        vector<TreeNode*> helpans;
        TreeNode* temp = NULL;
        helpans.push_back(root);
        while (!helpans.empty()) {
            temp = helpans.back();
            reverse.push_back(temp->val);
            helpans.pop_back();
            if (temp->left != NULL)
                helpans.push_back(temp->left);
            if (temp->right != NULL)
                helpans.push_back(temp->right);
        }
        while (!reverse.empty()) {
            ans.push_back(reverse.back());
            reverse.pop_back();
        }
        return ans;
    }
};

讲一下算法流程

预处理：头节点入栈

----------------------------------------------------------------------------------------------------------

1) cur节点入逆序栈

2) 弹出cur节点

3) cur左节点入栈，cur右节点入栈

----------------------------------------------------------------------------------------------------------

栈空时跳出

逆序栈依次压入ans中