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

一、题目

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

二、题解

思路：递归 / 哈希表 / 二叉树构造

1. 核心思路

前序遍历的第一个节点，一定是当前子树的根节点。

找到根节点后，可以在中序遍历中确定它的位置：

  • 根节点左边的元素属于左子树
  • 根节点右边的元素属于右子树

然后继续递归构造左子树和右子树。

为了快速找到根节点在 inorder 中的位置，可以使用 HashMap 存储：

节点值 -> 节点在 inorder 中的下标

这样每次查找根节点位置的时间复杂度就是 O(1)O(1)。

2. 具体步骤

  1. 使用 HashMap 记录 inorder 中每个节点值对应的下标。
  2. 使用变量 preorderIndex 记录当前前序遍历访问到的位置。
  3. 每次从 preorder 中取出当前节点作为根节点。
  4. 在 inorder 中找到根节点的位置 rootIndex。
  5. 根据 rootIndex 将中序遍历区间分成左子树和右子树。
  6. 递归构造左子树和右子树。
  7. 返回当前根节点。

3. 关键逻辑

前序遍历的顺序是：

根节点 -> 左子树 -> 右子树

所以每次先从 preorder 中取出一个值作为根节点。

中序遍历的顺序是：

左子树 -> 根节点 -> 右子树

所以根节点在 inorder 中的位置，可以把当前区间分成两部分：

[left, rootIndex - 1] 是左子树
[rootIndex + 1, right] 是右子树

关键递归逻辑：

  • 如果 left > right，说明当前区间为空，返回 null。
  • 否则，取 preorder[preorderIndex] 作为根节点。
  • 然后 preorderIndex++，继续处理下一个节点。
  • 先递归构造左子树，再递归构造右子树。

为什么要先构造左子树，再构造右子树？

因为前序遍历的顺序是：

根节点 -> 左子树 -> 右子树

所以当我们取完根节点后，preorder 中接下来出现的节点一定属于左子树。

三、代码

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

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */

class Solution {

    // 记录 inorder 中每个节点值对应的下标
    private Map<Integer, Integer> inorderIndexMap = new HashMap<>();

    // 记录当前 preorder 访问到的位置
    private int preorderIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 1. 处理特殊情况
        if (preorder == null || inorder == null || preorder.length == 0) {
            return null;
        }

        // 2. 将 inorder 中的值和下标存入哈希表
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }

        // 3. 构造整棵树
        return build(preorder, 0, inorder.length - 1);
    }

    /**
     * 根据 inorder 的区间 [left, right] 构造当前子树
     */
    private TreeNode build(int[] preorder, int left, int right) {
        // 如果区间为空，说明当前没有节点
        if (left > right) {
            return null;
        }

        // preorder 当前节点就是根节点
        int rootVal = preorder[preorderIndex];
        preorderIndex++;

        // 创建当前根节点
        TreeNode root = new TreeNode(rootVal);

        // 找到根节点在 inorder 中的位置
        int rootIndex = inorderIndexMap.get(rootVal);

        // 先构造左子树
        root.left = build(preorder, left, rootIndex - 1);

        // 再构造右子树
        root.right = build(preorder, rootIndex + 1, right);

        return root;
    }
}

四、复杂度分析

时间复杂度：O(n)O(n)

说明：每个节点只会被创建一次，HashMap 查询根节点位置的时间复杂度是 O(1)O(1)，所以总时间复杂度是 O(n)O(n)。

空间复杂度：O(n)O(n)

说明：HashMap 需要存储 n 个节点的位置。递归调用栈在最坏情况下也可能达到 O(n)O(n)。

评论