力扣（105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树）

题目1链接
题目1：

思路：使用前序确定根，使用中序分左右子树，分治法。

难点：如何控制递归确定左右子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

 //遍历前序确定根，使用中序来分树

class Solution {
public:

    TreeNode* findRoot(vector<int>& preorder, vector<int>& inorder, int& preindex, int left, int right)
    {
        if(left>right)
        {
            return nullptr;
        }
        //首先前序确定根
        TreeNode* root = new TreeNode(preorder[preindex]);

        //遍历中序，找根，分左右
        int rootindex = left;
        while(rootindex<=right)
        {
            if(inorder[rootindex] == preorder[preindex])
                break;  //找到了！
            rootindex++;
        }
        preindex++;

        //   [left, rootindex-1] rootindex [rootindex+1, right]
        root->left = findRoot(preorder, inorder, preindex, left, rootindex-1);
        root->right = findRoot(preorder, inorder, preindex, rootindex+1, right);
        return root;

    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return findRoot(preorder, inorder, i,0, inorder.size()-1);
    }
};

题目2链接

题目2：

题目1会了，题目二就一定会了！

注意：后序（左右根）从后往前确定根，中序分左右子树。
递归时，先遍历右子树，再遍历左子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* findRoot(vector<int>& inorder, vector<int>& postorder, int& postindex, int left, int right)
    {
        if(left>right)
        {
            return nullptr;
        }
        //首先后序确定根
        TreeNode* root = new TreeNode(postorder[postindex]);

        //遍历中序，找根，分左右
        int rootindex = left;
        while(rootindex<=right)
        {
            if(inorder[rootindex] == postorder[postindex])
                break;  //找到了！
            rootindex++;
        }
        postindex--;

        //   [left, rootindex-1] rootindex [rootindex+1, right]
        root->right = findRoot(inorder, postorder, postindex, rootindex+1, right);
        root->left = findRoot(inorder, postorder, postindex, left, rootindex-1);
        return root;

    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i = postorder.size() - 1;
        return findRoot(inorder, postorder, i, 0, inorder.size()-1);
    }
};