题解 | #实现二叉树先序，中序和后序遍历#

    vector<vector<int> > threeOrders(TreeNode* root) {
        return {preOrder(root),inOrder(root),postOrder(root)};
    }
    vector<int> preOrder(TreeNode* root)
    {
        stack<TreeNode* > s;
        vector<int> v;
        s.push(root);
        while(!s.empty())
        {
            TreeNode* p=s.top();
            s.pop();
            v.push_back(p->val);
            if(p->right)
                s.push(p->right);
            if(p->left)
                s.push(p->left);
        }
        return v;
    }
    vector<int> inOrder(TreeNode* root)
    {
        stack<TreeNode* > s;
        vector<int> v;
        s.push(root);
        TreeNode* pre=root;
        while(!s.empty())
        {
            TreeNode* p=s.top();
            if(p->left&&p->left!=pre&&p->right!=pre)//左孩子不为空，且左右孩子没有被遍历
                s.push(p->left);
            else if(p->right==pre)//刚遍历了右孩子
            {
                s.pop();
                pre=p;
            }
            else if(!p->left||p->left==pre)//左孩子为空或者左孩子被遍历,且右孩子未遍历
            {
                v.push_back(p->val);
                pre=p;
                if(p->right)
                    s.push(p->right);
                else 
                    s.pop();
            }
        }
        return v;
    }
    vector<int> postOrder(TreeNode* root)
    {
        stack<TreeNode* > s;
        vector<int> v;
        s.push(root);
        TreeNode* pre=root;
        while(!s.empty())
        {
            TreeNode* p=s.top();
            if(p->left&&p->left!=pre&&p->right!=pre)//左孩子不为空，且左右孩子没有被遍历
                s.push(p->left);
            else if(p->right==pre)//刚遍历了右孩子
            {
                v.push_back(p->val);
                pre=p;
                s.pop();
            }
            else if(!p->left||p->left==pre)//左孩子为空或者左孩子被遍历,且右孩子未遍历
            {
                if(p->right)
                    s.push(p->right);
                else//左孩子为空或已遍历，且右孩子为空
                {
                    v.push_back(p->val);
                    pre=p;
                    s.pop();
                }
            }
        }
        return v;
    }