题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

参考代码

/*
 * 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 {
    unordered_map<int, int> map;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

        for(int i = 0; i < inorder.size(); i++)
        {
            map[inorder[i]] = i;
        }

        //前序遍历的第一个元素是根节点
        TreeNode *root = new TreeNode(preorder[0]);
         // 继续遍历前序遍历序列中的其它元素
        for(int i = 1 ; i < preorder.size() ; i++){

            // 把当前遍历的元素构造为一个二叉树的节点
            TreeNode *node = new TreeNode(preorder[i]);

            // 把构造的节点插入到以 root 为根节点的二叉树中
            insertNode(root,node);

        }

        // 当 preorder 中所有元素都构造并且插入完毕之后
        // 二叉树就完成了构建
        return root;
    }

    void insertNode(TreeNode *root,TreeNode *node){

            // 当 root 和 node 指向的节点相同时，跳出循环
            while(root != node){

                // 如果 node 的中序遍历序列位置小于 root 的中序遍历序列位置
                // 说明 node 应该在 root 的左子树中
                if(map[node->val] < map[root->val]){

                    // 如果此时 root 没有左子树
                    if(root->left  NULL){
                        // 那么就把 node 设置为 root 的左子树
                        root->left = node;
                    }

                    root = root->left;


                }else{

                    // 如果 node 的中序遍历序列位置大于 root 的中序遍历序列位置
                    // 说明 node 应该在 root 的右子树中

                    // 如果此时 root 没有右子树
                    if(root->right  NULL){
                        // 那么就把 node 设置为 root 的右子树
                        root->right = node;
                    }

                    // 把 root 指向 root.right ，继续遍历 root 的右子树的情况
                    root = root->right;

                }
            }
    }
};