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

Categories:

Tags:

题目描述
思路分析
1. 解法一：递归 + 哈希表（推荐）
2. 解法二：迭代 + 栈
相似题目

题目描述

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

思路分析

解法一：递归 + 哈希表（推荐）

核心思路：

前序遍历的首元素永远是当前子树的根节点（根 → 左子树 → 右子树）

中序遍历中根节点将数组一分为二：左侧为左子树，右侧为右子树（左子树 → 根 → 右子树）

利用上述性质递归分治：取前序首元素为根，在中序中定位该根，由此切分左右子树的范围，再递归构造

哈希表优化：预先将中序遍历的 {值 → 下标} 存入哈希表，将每次定位根节点的操作从 O(n) 降至 O(1)，整体时间复杂度从 O(n²) 降至 O(n)

使用下标边界而非数组切片传递子问题，避免额外的数组拷贝开销

复杂度分析：

时间复杂度：O(n)，其中 n 为节点总数，每个节点恰好被处理一次

空间复杂度：O(n)，哈希表占用 O(n)，递归调用栈最深 O(n)（退化为链表时）

class Solution {

  // 存储中序遍历的值到下标映射，加速根节点定位
  private Map<Integer, Integer> inMap = new HashMap<>();

  public TreeNode buildTree(int[] preorder, int[] inorder) {
    // 预处理：将中序遍历的值与下标存入哈希表
    for (int i = 0; i < inorder.length; i++) {
      inMap.put(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
  }

  private TreeNode build(int[] pre, int preLeft, int preRight, int inLeft, int inRight) {
    // 递归终止：区间为空
    if (preLeft > preRight) {
      return null;
    }
    // 前序遍历的第一个元素是当前子树的根节点
    int rootVal = pre[preLeft];
    // 在中序遍历中定位根节点
    int inRootIdx = inMap.get(rootVal);
    // 左子树的节点个数
    int leftSize = inRootIdx - inLeft;
    TreeNode root = new TreeNode(rootVal);
    // 递归构造左子树：前序范围 [preLeft+1, preLeft+leftSize]，中序范围 [inLeft, inRootIdx-1]
    root.left = build(pre, preLeft + 1, preLeft + leftSize, inLeft, inRootIdx - 1);
    // 递归构造右子树：前序范围 [preLeft+leftSize+1, preRight]，中序范围 [inRootIdx+1, inRight]
    root.right = build(pre, preLeft + leftSize + 1, preRight, inRootIdx + 1, inRight);
    return root;
  }
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	// 预处理：将中序遍历的值与下标存入哈希表
	inMap := make(map[int]int, len(inorder))
	for i, val := range inorder {
		inMap[val] = i
	}

	var build func(preLeft, preRight, inLeft, inRight int) *TreeNode
	build = func(preLeft, preRight, inLeft, inRight int) *TreeNode {
		// 递归终止：区间为空
		if preLeft > preRight {
			return nil
		}
		// 前序遍历的第一个元素是当前子树的根节点
		rootVal := preorder[preLeft]
		// 在中序遍历中定位根节点
		inRootIdx := inMap[rootVal]
		// 左子树的节点个数
		leftSize := inRootIdx - inLeft
		root := &TreeNode{Val: rootVal}
		// 递归构造左子树
		root.Left = build(preLeft+1, preLeft+leftSize, inLeft, inRootIdx-1)
		// 递归构造右子树
		root.Right = build(preLeft+leftSize+1, preRight, inRootIdx+1, inRight)
		return root
	}

	return build(0, len(preorder)-1, 0, len(inorder)-1)
}

解法二：迭代 + 栈

核心思路：

用一个栈模拟前序遍历的递归过程，同时用指针 inIdx 追踪中序遍历的当前位置

依次遍历前序数组，将节点压栈；当栈顶节点的值等于 inorder[inIdx] 时，说明已遍历完该节点的整个左子树，弹栈并将 inIdx 右移，直到不匹配，此时下一个前序节点应作为最后弹出节点的右子节点

若栈顶节点值不等于 inorder[inIdx]，则当前前序节点为栈顶节点的左子节点

复杂度分析：

时间复杂度：O(n)，其中 n 为节点总数，每个节点入栈出栈各一次

空间复杂度：O(n)，栈的最大深度为 O(n)

class Solution {

  public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) {
      return null;
    }
    TreeNode root = new TreeNode(preorder[0]);
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    // 中序遍历的当前指针
    int inIdx = 0;
    for (int i = 1; i < preorder.length; i++) {
      TreeNode cur = new TreeNode(preorder[i]);
      TreeNode top = stack.peek();
      // 栈顶节点值不等于中序当前值，说明当前节点是栈顶的左子节点
      if (top.val != inorder[inIdx]) {
        top.left = cur;
      } else {
        // 弹出所有与中序匹配的节点，找到当前节点应挂在哪个节点的右侧
        TreeNode last = null;
        while (!stack.isEmpty() && stack.peek().val == inorder[inIdx]) {
          last = stack.pop();
          inIdx++;
        }
        last.right = cur;
      }
      stack.push(cur);
    }
    return root;
  }
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	root := &TreeNode{Val: preorder[0]}
	stack := []*TreeNode{root}
	// 中序遍历的当前指针
	inIdx := 0
	for i := 1; i < len(preorder); i++ {
		cur := &TreeNode{Val: preorder[i]}
		top := stack[len(stack)-1]
		// 栈顶节点值不等于中序当前值，说明当前节点是栈顶的左子节点
		if top.Val != inorder[inIdx] {
			top.Left = cur
		} else {
			// 弹出所有与中序匹配的节点，找到当前节点应挂在哪个节点的右侧
			var last *TreeNode
			for len(stack) > 0 && stack[len(stack)-1].Val == inorder[inIdx] {
				last = stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				inIdx++
			}
			last.Right = cur
		}
		stack = append(stack, cur)
	}
	return root
}

相似题目

题目	难度	考察点
106. 从中序与后序遍历序列构造二叉树	中等	二叉树、分治、哈希表
889. 根据前序和后序遍历构造二叉树	中等	二叉树、分治
1008. 前序遍历构造二叉搜索树	中等	二叉搜索树、递归
297. 二叉树的序列化与反序列化	困难	二叉树重建、BFS/DFS
654. 最大二叉树	中等	递归分治构造二叉树
114. 二叉树展开为链表	中等	二叉树、前序遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/36989078