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

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000

inorder.length == preorder.length

-3000 <= preorder[i], inorder[i] <= 3000

preorder 和 inorder 均 无重复 元素

inorder 均出现在 preorder

preorder 保证 为二叉树的前序遍历序列

inorder 保证 为二叉树的中序遍历序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // [root, 左, 右]
        // [左, root, 右]
        return helper(preorder, inorder, 0, preorder.size(), 0, inorder.size());
    }
    TreeNode *helper(vector<int> &preorder, vector<int> &inorder, int l1,
                     int r1, int l2, int r2) {
        if (l1 >= r1 || l2 >= r2)
            return nullptr;

        TreeNode *root = new TreeNode(preorder[l1]);

        int leftLen = 0;
        for (int i = l2; i < r2; i++) {
            leftLen++;
            if (inorder[i] == preorder[l1]) {
                break;
            }
        }

        root->left = helper(preorder, inorder, l1 + 1, l1 + leftLen, l2,
                            l2 + leftLen - 1);
        root->right =
            helper(preorder, inorder, l1 + leftLen, r1, l2 + leftLen, r2);

        return root;
    }
};