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

给定两个整数数组 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]

Solution

前序遍历：按照「根-左子树-右子树」的顺序遍历二叉树。

中序遍历：按照「左子树-根-右子树」的顺序遍历二叉树。

前序遍历可以确定根的位置，根据根的位置，在中序遍历中又可以确定左右子树的位置，然后根据前序遍历，又可以确定左右子树中根的位置，这实际上是一个递归问题

先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素

先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        Map<Integer, Integer> index = new HashMap<>(n); // 预分配空间
        for (int i = 0; i < n; i++) {
            index.put(inorder[i], i);
        }
        return dfs(preorder, 0, n, inorder, 0, n, index); // 左闭右开区间
    }

    private TreeNode dfs(int[] preorder, int preL, int preR, int[] inorder, int inL, int inR, Map<Integer, Integer> index) {
        if (preL == preR) { // 空节点
            return null;
        }
        int leftSize = index.get(preorder[preL]) - inL; // 左子树的大小
         //左子树在前序遍历中的大小[pre+1,pre+1+leftSize),pre的位置是根节点,中序遍历中大小为[inL,inL+leftSize),inL+leftSize的位置是根节点
        TreeNode left = dfs(preorder, preL + 1, preL + 1 + leftSize, inorder, inL, inL + leftSize, index);
        //右子树在前序遍历中的大小[pre+1+leftSize,preR),在中序遍历中的大小为[inL+1+leftSize,inR)
        TreeNode right = dfs(preorder, preL + 1 + leftSize, preR, inorder, inL + 1 + leftSize, inR, index);
        return new TreeNode(preorder[preL], left, right);
    }
}