leetcode105：从前序与中序遍历构建二叉树

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

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

步骤1：定义问题和条件

题目计算问题性质

给定二叉树的 先序遍历（preorder）和 中序遍历（inorder），构造该二叉树并返回其根节点。

• 先序遍历特点：遍历顺序是根节点 -> 左子树 -> 右子树。
• 中序遍历特点：遍历顺序是左子树 -> 根节点 -> 右子树。

输入输出条件

• 输入：
  • preorder: 二叉树的先序遍历结果数组。
  • inorder: 二叉树的中序遍历结果数组。
• 输出：
  • 构造出的二叉树的根节点。

限制条件

1. 两个数组长度相等，且 1 <= preorder.length == inorder.length <= 3000。
2. 数组中没有重复元素。
3. inorder 数组中的所有元素都能在 preorder 中找到。
4. 保证给定的遍历结果能构成唯一的二叉树。

边界条件

1. 数组只有一个元素时，直接返回单节点的树。
2. 数组为空时，返回空树。

步骤2：解题思路与算法设计

最佳算法设计：分治法

利用先序和中序遍历的特点，可以通过递归实现二叉树的构造。

1. 核心逻辑：

   • 先序遍历的第一个元素一定是当前树的根节点。
   • 在中序遍历中找到该根节点的位置，该位置将中序数组分为两部分：
     • 左部分为根节点的左子树的中序遍历。
     • 右部分为根节点的右子树的中序遍历。
   • 递归地对上述左右部分继续执行分治构造。

2. 步骤详解：

   • 从 preorder 数组中取根节点。
   • 在 inorder 中找到该根节点的索引，划分出左子树和右子树的元素。
   • 根据划分出的中序结果计算出左右子树在先序数组中的范围。
   • 递归构造左右子树，直到范围为空。

3. 时间复杂度：

   • 每次递归需在线性时间内找到根节点在 inorder 中的位置，优化后为 $O(1)$（使用哈希表）。
   • 整体时间复杂度为 $O(n)$。

4. 空间复杂度：

   • 递归栈的深度为树的高度，最坏情况下（单链树）空间复杂度为 $O(n)$。

步骤3：实现代码

步骤4：优化和启发

算法优化点

• 哈希表加速查找：通过哈希表记录中序数组中每个值的索引，从 $O(n)$ 优化为 $O(1)$。
• 递归分治思想：利用遍历的分区特点递归构造，避免额外的数据结构存储。

启发

• 分治法适合解决问题规模大、递归特性明显的问题。
• 通过提前构建哈希表优化重复查找，是降低算法时间复杂度的重要思路。

步骤5：实际应用场景

应用场景

• 数据结构恢复：从线性序列中重建树形结构，在数据库索引或图形数据中应用广泛。
• 二叉树传输：用于二叉树的序列化和反序列化（如二叉搜索树）。

案例分析

• 网络通信中的 XML/JSON 树还原：
  • 在实际中，XML/JSON 数据可以表示为树结构。
  • 通过序列化传输（生成先序和中序遍历结果），接收端通过算法构造原始树结构。
  • 优化后的算法可显著提高大规模数据传输中的效率。