从前序与中序遍历序列构造二叉树

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

示例 1:

img

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

示例 2:

1
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
31
32

class Solution {
    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 因为头结点能够在前序序列快速查找，但不能在中序序列快速查找
        // 所以哈希表记录中序序列中值和下标的对应关系
        for (int i = 0; i < n; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode build(int[] preorder, int[] inorder, int pl, int pr, int il, int ir) {
        if (pl > pr || il > ir) {
            return null;
        }
        // 根节点的值
        int rootVal = preorder[pl];
        // 找到根节点在中序序列中的下标
        int rootInorder = map.get(rootVal);
        // 左子树的节点个数
        int leftSize = rootInorder - il;
        // 右子树的节点个数
        int rightSize = ir - leftSize - 1;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, inorder, pl + 1, pl + leftSize, il, rootInorder - 1);
        root.right = build(preorder, inorder, pl + leftSize + 1, pr, rootInorder + 1, ir);
        return root;
    }
}