leetcode145.二叉树的后序遍历（简单）

注意：非递归的效率要高于递归的效率

方法一：递归

class Solution {
public:
    void postorder(vector &ans, TreeNode* root);
    vector postorderTraversal(TreeNode* root) {
        vector ans;
        postorder(ans, root);
        return ans;
    }
};
void Solution :: postorder(vector &ans, TreeNode* root) {
    if (root == nullptr) return ;
    postorder(ans, root->left);
    postorder(ans, root->right);
    ans.push_back(root->val);
}

方法二：两个栈实现非递归
思想：
两个栈stk1 stk2实现：初始将root压入stk1，然后栈顶出栈stk1入栈到stk2，同时将该元素的左孩子，右孩子依次压入stk1，重复此过程直到stk1为空，依次出栈stk2的元素得到的就是后序序列

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        
        stack stk1, stk2;
        vector ans;
        if (!root) return ans;
        stk1.push(root);
        while (!stk1.empty()) {
            TreeNode* top = stk1.top();
            stk1.pop();
            stk2.push(top);
            if (top->left) stk1.push(top->left);
            if (top->right) stk1.push(top->right);
        }
        while (!stk2.empty()) {
            ans.push_back(stk2.top()->val);
            stk2.pop();
        }
        return ans;
    }
};

方法三：一个栈实现非递归
top保存的是父结点
pre保存的是上一个访问的结点
root保存的是当前要遍历的结点

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        stack stk;
        TreeNode* pre = nullptr; //pre保存前一个访问的结点，root表示当前正在指向的结点
        vector ans;
        while (root || !stk.empty()) {
            while (root) {
                stk.push(root);
                root = root->left;
            }
            TreeNode* top = stk.top(); //保存父节点，如果不访问右结点的话就出栈，否则就不出栈
            if (top->right == nullptr || top->right == pre) { //如果右子树为空或者从右子树返回来的则继续出栈下一个
                ans.push_back(top->val);
                stk.pop();
                pre = top;
                root = nullptr;
            }else { //否则遍历右子树
                root = top->right;
            }
        }
        return ans;
    }
};