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

//借助了先序非递归的方法,第一个循环就是对先序的改写了
//先序遍历时,弹出栈顶节点就访问,然后先压右孩子再压左孩子,循环直到栈空
//改写如下:
//如果每次弹出栈顶元素就访问,并且先压左孩子再压右孩子,那么整体的访问顺序就是头右左;而后续遍历的顺序是啥?
//不就是左右头嘛?和头右左是逆序的,那我们在每次弹出栈顶元素不访问,将它压入另一个栈,另一个栈的顺序就是后续遍历了
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s1,s2;
        vector<int> v;
        if(root==nullptr) return v;
        s1.push(root);
	  //先序遍历改写
        while(!s1.empty())
        {
            TreeNode* t = s1.top();
            s1.pop();
            s2.push(t);//弹出不访问,压入s2
            if(t->left)//先压入左
                s1.push(t->left);
            if(t->right)//再压入右
                s1.push(t->right);
        }
        while(!s2.empty())//访问s2
        {
            v.push_back(s2.top()->val);
            s2.pop();
        }
        return v;
    }
};