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

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:

    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */

    // 定义三个一维数组
    vector<int> pre;
    vector<int> in;
    vector<int> pos;



    // 递归函数一
    void preorder(TreeNode* root)
    {
        if(root != nullptr)
        {
            pre.push_back(root->val);
            preorder(root->left);
            preorder(root->right);
        }
    }

    // 递归函数二
    void inorder(TreeNode* root)
    {
        if (root != nullptr)
        {
            inorder(root->left);
            in.push_back(root->val);
            inorder(root->right);
        }
    }

    // 递归函数三
    void posorder(TreeNode* root)
    {
        if (root != nullptr)
        {
            posorder(root->left);
            posorder(root->right);
            pos.push_back(root->val);
        }
    }



    // 迭代函数一(使用了一个栈)
    void preorder2(TreeNode* root)
    {
        if (root != nullptr)
        {
            stack<TreeNode*> stk1;
            stk1.push(root);

            while(!stk1.empty())
            {
                root = stk1.top(); // 用root方便进行表示
                pre.push_back(root->val);
                stk1.pop();

                if (root->right != nullptr)
                    stk1.push(root->right);
                if (root->left != nullptr)
                    stk1.push(root->left);
            }
        }
    }

    // 迭代函数二(使用了一个栈)
    void inorder2(TreeNode* root)
    {
        if (root != nullptr)
        {
            stack<TreeNode*> stk1;

            while(!stk1.empty() || root != nullptr)
            {
                if (root != nullptr)
                {
                    stk1.push(root);
                    root = root->left;
                }
                else
                {
                    root = stk1.top();
                    in.push_back(root->val);
                    stk1.pop();
                    root = root->right;
                }
            }
        }
    }


    // 迭代函数三(使用了两个栈)
    void posorder2(TreeNode* root)
    {
        if (root != nullptr)
        {
            stack<TreeNode*> stk1;
            stack<TreeNode*> stk2; // 第二个栈起到了反序的作用
            stk1.push(root);

            while(!stk1.empty())
            {
                root = stk1.top();
                stk2.push(root);
                stk1.pop();

                if (root->left != nullptr)
                    stk1.push(root->left);
                if (root->right != nullptr)
                    stk1.push(root->right);
            }
            while(!stk2.empty())
            {
                pos.push_back(stk2.top()->val);
                stk2.pop();
            }
        }
    }



    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here

        // 二维数组的操作
        vector<vector<int>> res;

        preorder2(root);
        res.push_back(pre);

        inorder2(root);
        res.push_back(in);

        posorder2(root);
        res.push_back(pos);

        return res;

    }
};