题目描述

根据前序遍历和中序遍历重建二叉树

样例

给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]

算法1

递归算法

1. 前序遍历的第一个数pre[0]就是二叉树的根节点
2. 找到根节点在中序遍历中的位置k,假设根节点左边的就是左子树的中序遍历，假设长度为l,右边为右子树的中序遍历，
   假设左子树的长度为l
3. 在前序遍历中根节点的后l个节点都是左子树的前序遍历，那么pre.size()-l～pre.size()的节点都是右子树的前序遍历。
4. 有了左右子树的前序遍历和中序遍历，我们可以先递归创建出左右子树，然后再创建根节点；
5. 使用哈希表unordered_map来记录节点在vector数组中的位置。

时间复杂度

$O(N)$

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:
    map<int,int>hash;
    vector<int> preorder,inorder;
    TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
        preorder=_preorder,inorder=_inorder;
        int n=inorder.size();
        //记录中序遍历中每个节点的下标
        for (int i = 0; i < n; i ++ )   hash[inorder[i]]=i;
        return dfs(0,preorder.size()-1,0,inorder.size()-1);
    }
    TreeNode* dfs(int pl,int pr,int il,int ir){

        if(pl>pr)   return nullptr;
        auto root= new TreeNode(preorder[pl]);
        int k=hash[root->val];
        auto left=dfs(pl+1,pl+k-il,il,k-1);
        auto right=dfs(pl+k-il+1,pr,k+1,ir);
        root->left=left,root->right=right;
        return root;
    }
};