【剑指 Offer.07 重建二叉树】

题目地址：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

比如：该二叉树

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

递归方法

可以知道的是：

前序遍历一棵二叉树的结果肯定是：

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

中序遍历一棵二叉树的结果是：

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

那么我们可以采取以下思路：

（设定先序遍历为preorder，中序遍历为inorder）

• 设定preorder[0] 为根节点 root
• 在 inorder 中寻找根节点所在的位置，然后计算 左子树 的结点个数
• 然后就可以递归建树了

---

代码如下：

class Solution {
public:
    unordered_map<int, int> index;
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i++) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode *myBuildTree(vector<int> &preorder, vector<int> &inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        int root_pre_idx = preorder_left;
        TreeNode *root = new TreeNode(preorder[root_pre_idx]);
        int root_in_idx = index[preorder[root_pre_idx]];
        int left_tree_cnt = root_in_idx - inorder_left;
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + left_tree_cnt, inorder_left, root_in_idx - 1);
        root->right = myBuildTree(preorder, inorder, preorder_left + left_tree_cnt + 1, preorder_right, root_in_idx + 1, inorder_right);
        return root;
    }
};