题目描述

blablabla

样例

blablabla

算法1

题目思路：

前序遍历的第一个节点就是根节点root,中序遍历中，找到root所在的位置，root左边的所有数是根的左子树，root右边的所有数是根的右子树。

找到前序遍历中左子树（设左子树有L个点）对应的那些数（前序遍历中，从第一个节点往后数L个数），右子树对应的那些数（剩下的那些数）。

左子树的前序遍历中，第一个点是左子树的根，左子树的中序遍历中，找到root所在的位置，root左边所有的数是根的左子树，root右边所有的数是根的右子树。

找到前序遍历中左子树（设左子树有L个点）对应的那些数（从根所在的位置，向后数L个），剩下的数（当前子树的总个数-L）都是右子树。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int> pos;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for(int i=0; i<n; i++){
            pos[inorder[i]] = i;
        }

        return dfs(preorder, inorder, 0, n-1, 0, n-1);
    }

    TreeNode* dfs(vector<int>& pre, vector<int> &in, int pl, int pr, int il, int ir){
        if(pl>pr) return NULL;
        int k = pos[pre[pl]];
        TreeNode* root = new TreeNode(in[k]);
        root->left = dfs(pre, in, pl+1, pl+1+k-il-1, il , k-1);
        root->right = dfs(pre, in,pl+k-il+1,pr,  k+1, ir);
        return root;
    }
};