当前位置：首页 > news >正文

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

news 2026/4/23 15:24:02

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

这道题的核心思路是利用先序遍历和中序遍历的特性递归构造二叉树：
1、先序遍历：根->左->右->（第一个元素一定是根节点）
2、中序遍历：左->根->右（根节点左侧是左子树，右侧是右子树）

代码核心解析：

1、哈希表优化

用HashMap存储中序遍历的值-索引映射，将查找根节点在中序数组中的位置的时间复杂度从O（n）降为O（1），整体时间复杂度优化为O（n）。

哈希表定义语法:
Map<Integer,Integer> inorderMap = new HashMap<>();
将中序数组存入哈希表的，用inorderMap.put(inorder[i],i),将值-索引存入哈希表

2、递归逻辑

终止条件：数组索引越界（preStart > preEnd || inStart > inEnd），说明没有节点需要构造，返回Null。
确定根节点：先序数组的第一个元素就是当前子树的根节点（根据先序遍历的特性根左右）
分割左右子树：
中序数组中，根节点左侧 = 左子树，右侧 = 右子树（左根右）
先序数组中，根节点后leftSize个元素 = 左子树，剩余元素 = 右子树
递归构造：分别递归构造左、右子树，挂载到根节点上

3、索引边界

左子树先序：[preStart+1, preStart+leftSize]
右子树先序：[preStart+leftSize+1, preEnd]
左子树中序：[inStart, rootIndex-1]
右子树中序：[rootIndex+1, inEnd]

复杂度分析：

时间复杂度：O(n)，n 是节点个数，仅遍历一次数组构建哈希表，递归每个节点仅访问一次
空间复杂度：O(n)，哈希表存储 n 个节点，递归调用栈最坏（链状二叉树）为 O(n)

完整代码实现如下：

import java.util.HashMap;
import java.util.Map;

// 二叉树节点定义
class TreeNode {

int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;
}

}

public class ConstructBinaryTree {
// 哈希表：存储中序遍历的值 -> 索引，快速定位根节点位置
private Map<Integer, Integer> inorderMap;

public TreeNode buildTree(int[] preorder, int[] inorder) {inorderMap = new HashMap<>();// 将中序数组存入哈希表，方便快速查找for (int i = 0; i < inorder.length; i++) {inorderMap.put(inorder[i], i);}// 递归构造二叉树return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}/*** 递归构造二叉树* @param pre 先序数组* @param preStart 先序数组起始索引* @param preEnd 先序数组结束索引* @param in 中序数组* @param inStart 中序数组起始索引* @param inEnd 中序数组结束索引* @return 构造的子树根节点*/
private TreeNode build(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {// 递归终止条件：索引越界，说明没有节点if (preStart > preEnd || inStart > inEnd) {return null;}// 1. 先序第一个节点就是当前子树的根节点int rootVal = pre[preStart];TreeNode root = new TreeNode(rootVal);// 2. 在中序数组中找到根节点的索引int rootIndex = inorderMap.get(rootVal);// 3. 计算左子树的节点个数int leftSize = rootIndex - inStart;// 4. 递归构造左子树// 先序：根节点后 leftSize 个元素是左子树// 中序：根节点左侧所有元素是左子树root.left = build(pre, preStart + 1, preStart + leftSize, in, inStart, rootIndex - 1);// 5. 递归构造右子树// 先序：左子树之后的元素是右子树// 中序：根节点右侧所有元素是右子树root.right = build(pre, preStart + leftSize + 1, preEnd, in, rootIndex + 1, inEnd);return root;
}// 测试代码
public static void main(String[] args) {ConstructBinaryTree solution = new ConstructBinaryTree();// 示例：先序遍历 [3,9,20,15,7]，中序遍历 [9,3,15,20,7]int[] preorder = {3,9,20,15,7};int[] inorder = {9,3,15,20,7};TreeNode root = solution.buildTree(preorder, inorder);System.out.println("二叉树构造完成，根节点值：" + root.val);
}

}

用 preorder = [3,9,20,15,7]，inorder = [9,3,15,20,7]，逐层级拆解递归过程，每一步都标注索引边界和节点构造逻辑。

初始调用
build(pre,0,4,in,0,4)

根节点值pre[0] = 3，在中序中 rootIndex = 1
左子树节点数 leftSize = 1 - 0 = 1
构造根节点3

1.递归构造左子树
调用:build(pre,0+1,0+1,in,0,1-1)→ build(pre, 1, 1, in, 0, 0)

根节点值pre[1] = 9，在中序中rootIndex = 0
左子树节点数left = 0-0 = 0
构造节点9
左子树调用：build(pre, 2, 1, in, 0, -1) → 索引越界，返回 null → 节点 9 的左孩子为 null
右子树调用：build(pre, 1+0+1, 1, in, 0+1, 0) → build(pre, 2, 1, in, 1, 0) → 索引越界，返回 null → 节点 9 的右孩子为 null
节点9挂载到根节点3的左孩子位置

2.递归构造右子树
调用：调用：build(pre, 0+1+1, 4, in, 1+1, 4) → build(pre, 2, 4, in, 2, 4)

递归过程核心规律

每一层递归只做 3 件事：