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

二叉树的先序、中序和后序遍历的要点是：左右顺序固定，先序是根节点最先访问，后序是根节点最后访问，即三种访问顺序是根据根节点的访问顺序来命名的。在访问时递归即可。
先序：根左右
中序：左根右
后序：左右根

/**
 * 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<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        vector<vector<int> > rst;

        rst.push_back(pre_order(root));
        rst.push_back(mid_order(root));
        rst.push_back(post_order(root));

        return rst;
    }

    //根左右
    vector<int> pre_order(TreeNode* root)
    {

        vector<int> rst;
        if(!root)
            return rst;

        //将根结点的val加入到rst中;
        rst.push_back(root->val);

        //如果有左孩子则统计左孩子;
        if(root->left)
            for(auto& o:pre_order(root->left))
                rst.push_back(o);

        //如果有右孩子则统计右孩子;
        if(root->right)
            for(auto& o:pre_order(root->right))
                rst.push_back(o);

        return rst;
    }

    //左根右
    vector<int> mid_order(TreeNode* root)
    {

        vector<int> rst;
        if(!root)
            return rst;

        //如果有左孩子则统计左孩子;
        if(root->left)
            for(auto& o:mid_order(root->left))
                rst.push_back(o);

        //将根结点的val加入到rst中;
        rst.push_back(root->val);

        //如果有右孩子则统计右孩子;
        if(root->right)
            for(auto& o:mid_order(root->right))
                rst.push_back(o);

        return rst;
    }

    //左右根
    vector<int> post_order(TreeNode* root)
    {

        vector<int> rst;
        if(!root)
            return rst;

        //如果有左孩子则统计左孩子;
        if(root->left)
            for(auto& o:post_order(root->left))
                rst.push_back(o);

        //如果有右孩子则统计右孩子;
        if(root->right)
            for(auto& o:post_order(root->right))
                rst.push_back(o);

        //将根结点的val加入到rst中;
        rst.push_back(root->val);

        return rst;
    }
};