大厂面试官不会告诉你-重建二叉树有这个捷径

在这里插入图片描述这是一道二叉树的经典问题，不仅考察对二叉树遍历的理解，更考验递归思维和边界处理能力。

核心思路

采用分治思想:

通过前序遍历确定根节点,在中序遍历中定位该根节点的位置,以此为分界点划分出左右子树的范围,然后递归地对左右子树重复这个过程,最终完成整棵树的重建。

索引计算的推导

假设:

1
2
3


前序遍历: pre[l1 ... r1]
中序遍历: in[l2 ... r2]
根节点在中序中的位置: k

1.中序遍历的划分

根节点 k 天然就是分界点:

1
2


中序: [l2 ... k-1] | k | [k+1 ... r2]
       ← 左子树 →   根   ← 右子树 →

左子树范围: in[l2, k-1]
右子树范围: in[k+1, r2]

2.前序遍历的划分

1
2


pre[l1] | pre[l1+1 ... ?] | pre[? ... r1]
  根节点     左子树          右子树

已知左子树有 k - l2 个节点，所以:

1
2


pre[l1] | pre[l1+1 ... l1+(k-l2)] | pre[l1+(k-l2)+1 ... r1]
  根         左子树(k-l2个节点)          右子树

左子树范围: pre[l1+1, l1+k-l2]
右子树范围: pre[l1+k-l2+1, r1]

拿示例1举例

假设输入:

1
2


前序遍历: [3, 9, 20, 15, 7]
中序遍历: [9, 3, 15, 20, 7]

第1步: 前序首元素 3 是根节点,在中序中位置为 1

1
2


中序: [9] | 3 | [15, 20, 7]
       左     根      右

第2步: 递归处理左子树 [9] 和右子树 [20, 15, 7]

第3步: 右子树中,20 是根节点,继续划分…

最终构建出:

代码实现

 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
33
34
35
36
37
38
39
40


public static TreeNode buildTree(int[] pre, int[] in) {
    // 边界检查
    if (pre == null || in == null || pre.length != in.length) {
        return null;
    }
    
    // 构建哈希表:值 → 在中序遍历中的索引
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < in.length; i++) {
        map.put(in[i], i);
    }
    
    return f(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
}

public static TreeNode f(int[] pre, int l1, int r1, 
                         int[] in, int l2, int r2, 
                         HashMap<Integer, Integer> map) {
    // 递归终止条件
    if (l1 > r1) {
        return null;
    }
    
    // 创建根节点
    TreeNode head = new TreeNode(pre[l1]);
    
    // 只有一个节点时直接返回
    if (l1 == r1) {
        return head;
    }
    
    // 在中序遍历中找到根节点位置
    int k = map.get(pre[l1]);
    
    // 递归构建左右子树
    head.left = f(pre, l1 + 1, l1 + k - l2, in, l2, k - 1, map);
    head.right = f(pre, l1 + k - l2 + 1, r1, in, k + 1, r2, map);
    
    return head;
}

如果觉得有帮助，欢迎点赞、关注、转发~