跳转至

12.3   构建二叉树问题

Question

给定一棵二叉树的前序遍历 preorder 和中序遍历 inorder ,请从中构建二叉树,返回二叉树的根节点。假设二叉树中没有值重复的节点(如图 12-5 所示)。

图 12-5   构建二叉树的示例数据

图解 12-5:由前序与中序序列重建五节点二叉树

由前序 [3,9,2,1,7] 与中序 [9,3,1,2,7],唯一重建以 3 为根的五节点二叉树。

已知一棵二叉树的前序遍历序列 preorder = [3, 9, 2, 1, 7] 和中序遍历序列 inorder = [9, 3, 1, 2, 7],且树中所有节点的值互不重复。

前序遍历遵循“根 → 左子树 → 右子树”的访问顺序,中序遍历遵循“左子树 → 根 → 右子树”的访问顺序。利用两条序列的互补位置关系,可以从中唯一还原整棵二叉树。

画面左侧展示待重建的目标二叉树:根节点为 3,其左子节点为 9、右子节点为 2;节点 2 的左子节点为 1、右子节点为 7;节点 9、1、7 均为叶节点。

画面右侧上下排列这两条遍历序列,并通过向左的箭头“重建二叉树”指向左侧树结构。结合遍历规则可印证:前序首元素 3 确定整棵树的根;在中序中,3 左侧仅有 9,说明左子树只含节点 9;3 右侧为 [1, 2, 7],对应前序后三项 [2, 1, 7],说明右子树以 2 为根、以 1 和 7 为左右子节点。

注意这是一棵普通二叉树而非二叉搜索树,节点位置由遍历次序决定,并不要求左子节点的值小于父节点(例如左子节点 9 大于根节点 3)。

前序负责定位子树根,中序负责划分子树成员范围;在节点值互不重复的前提下,二者共同唯一确定这棵树。

1.   判断是否为分治问题

原问题定义为从 preorder 和 inorder 构建二叉树,是一个典型的分治问题。

  • 问题可以分解:从分治的角度切入,我们可以将原问题划分为两个子问题:构建左子树、构建右子树,加上一步操作:初始化根节点。而对于每棵子树(子问题),我们仍然可以复用以上划分方法,将其划分为更小的子树(子问题),直至达到最小子问题(空子树)时终止。
  • 子问题是独立的:左子树和右子树是相互独立的,它们之间没有交集。在构建左子树时,我们只需关注中序遍历和前序遍历中与左子树对应的部分。右子树同理。
  • 子问题的解可以合并:一旦得到了左子树和右子树(子问题的解),我们就可以将它们链接到根节点上,得到原问题的解。

2.   如何划分子树

根据以上分析,这道题可以使用分治来求解,但如何通过前序遍历 preorder 和中序遍历 inorder 来划分左子树和右子树呢?

根据定义,preorder 和 inorder 都可以划分为三个部分。

  • 前序遍历:[ 根节点 | 左子树 | 右子树 ] ,例如图 12-5 的树对应 [ 3 | 9 | 2 1 7 ] 。
  • 中序遍历:[ 左子树 | 根节点 | 右子树 ] ,例如图 12-5 的树对应 [ 9 | 3 | 1 2 7 ] 。

以上图数据为例,我们可以通过图 12-6 所示的步骤得到划分结果。

  1. 前序遍历的首元素 3 是根节点的值。
  2. 查找根节点 3 在 inorder 中的索引,利用该索引可将 inorder 划分为 [ 9 | 3 | 1 2 7 ] 。
  3. 根据 inorder 的划分结果,易得左子树和右子树的节点数量分别为 1 和 3 ,从而可将 preorder 划分为 [ 3 | 9 | 2 1 7 ] 。

图 12-6   在前序遍历和中序遍历中划分子树

图解 12-6:用中序位置切分左右子树,再切分前序

前序首项 3 定根,中序分出左子树 [9] 与右子树 [1,2,7],再按节点数切分前序。

输入为前序遍历 preorder = [3, 9, 2, 1, 7] 与中序遍历 inorder = [9, 3, 1, 2, 7],所有节点值互不重复。

前序先访问根,因此前序首元素 3 就是根。

在中序中找到 3;它左边只有 [9],右边是 [1,2,7],所以左右子树分别有 1 个和 3 个节点。

据此切分前序:根 3 之后的一个元素 [9] 属于左子树,其余 [2,1,7] 属于右子树。右子树的两种遍历包含相同节点,访问顺序不同。

画面左侧还画出供对照的完整五节点树。下方第一张表列出本次切分的子问题序列,第二张表列出图中树的全部连接。

左右子问题的遍历序列
部分节点数前序中序
根1[3][3]
左子树1[9][9]
右子树3[2,1,7][1,2,7]
完整树的连接
节点左子节点右子节点
392
9无无
217
1无无
7无无

原问题由此分为左右两个独立的递归子问题。

3.   基于变量描述子树区间

根据以上划分方法,我们已经得到根节点、左子树、右子树在 preorder 和 inorder 中的索引区间。而为了描述这些索引区间,我们需要借助几个指针变量。

  • 将当前树的根节点在 preorder 中的索引记为 \(i\) 。
  • 将当前树的根节点在 inorder 中的索引记为 \(m\) 。
  • 将当前树在 inorder 中的索引区间记为 \([l, r]\) 。

如表 12-1 所示,通过以上变量即可表示根节点在 preorder 中的索引,以及子树在 inorder 中的索引区间。

表 12-1   根节点和子树在前序遍历和中序遍历中的索引

根节点在 preorder 中的索引 子树在 inorder 中的索引区间
当前树 \(i\) \([l, r]\)
左子树 \(i + 1\) \([l, m-1]\)
右子树 \(i + 1 + (m - l)\) \([m+1, r]\)

请注意,右子树根节点索引中的 \((m-l)\) 的含义是“左子树的节点数量”,建议结合图 12-7 理解。

图 12-7   根节点和左右子树的索引区间表示

图解 12-7:用 i、l、m、r 表示构树递归的索引区间

左子树根的前序索引为 i+1,右子树根的前序索引为 i+1+(m−l),其中 m−l 为左子树节点数。

输入为前序遍历 preorder = [3, 9, 2, 1, 7] 与中序遍历 inorder = [9, 3, 1, 2, 7],节点值互不重复。

数组索引从 0 开始:i 表示当前子树根节点在 preorder 中的索引;[l, r] 表示当前子树在 inorder 中的闭区间;m 表示当前子树根节点在 inorder 中的索引。注意 m 是通过根的值在 inorder(或哈希表)中查表得到的索引,并非区间 [l, r] 的几何中点。

画面标出顶层调用的符号指针。按数组从 0 起编号可读得:根 3 的前序索引 i = 0,中序闭区间 [l, r] = [0, 4],根在中序中的索引 m = 1。因而左子树节点数 m − l = 1;这些数字索引是按图中位置换算的,图上主要标示符号。

左子树根紧跟当前根,前序索引为 i + 1。右子树根需跳过当前根及全部 m − l 个左子树节点,前序索引为 i + 1 + (m − l)。

左侧对应的树以 3 为根,左子为 9、右子为 2,2 的左、右子节点为 1、7;9、1、7 是叶节点。递归实现中遇到 l > r 的空中序区间时,调用直接返回空子树。下表公式中的 i、l、m、r 都指当前父调用;末列给出相应子问题的具体前序根索引和中序区间。

递归参数的通式与本例
子问题前序根索引中序闭区间本例
当前树i[l,r]前序根索引 0,中序区间 [0,4],根值 3;根的中序索引 m=1
左子树i+1[l,m−1]前序根索引 1,中序区间 [0,0],根值 9
右子树i+1+(m−l)[m+1,r]前序根索引 2,中序区间 [2,4],根值 2

借助指针变量 i、l、m、r 的代数关系,每次递归调用仅需传递整数索引即可精确界定左右子树,无需切片复制子数组。

4.   代码实现

为了提升查询 \(m\) 的效率,我们借助一个哈希表 hmap 来存储数组 inorder 中元素到索引的映射:

build_tree.py
def dfs(
    preorder: list[int],
    inorder_map: dict[int, int],
    i: int,
    l: int,
    r: int,
) -> TreeNode | None:
    """构建二叉树:分治"""
    # 子树区间为空时终止
    if r - l < 0:
        return None
    # 初始化根节点
    root = TreeNode(preorder[i])
    # 查询 m ,从而划分左右子树
    m = inorder_map[preorder[i]]
    # 子问题:构建左子树
    root.left = dfs(preorder, inorder_map, i + 1, l, m - 1)
    # 子问题:构建右子树
    root.right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r)
    # 返回根节点
    return root

def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
    """构建二叉树"""
    # 初始化哈希表,存储 inorder 元素到索引的映射
    inorder_map = {val: i for i, val in enumerate(inorder)}
    root = dfs(preorder, inorder_map, 0, 0, len(inorder) - 1)
    return root
build_tree.cpp
/* 构建二叉树:分治 */
TreeNode *dfs(vector<int> &preorder, unordered_map<int, int> &inorderMap, int i, int l, int r) {
    // 子树区间为空时终止
    if (r - l < 0)
        return NULL;
    // 初始化根节点
    TreeNode *root = new TreeNode(preorder[i]);
    // 查询 m ,从而划分左右子树
    int m = inorderMap[preorder[i]];
    // 子问题:构建左子树
    root->left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // 子问题:构建右子树
    root->right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // 返回根节点
    return root;
}

/* 构建二叉树 */
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    // 初始化哈希表,存储 inorder 元素到索引的映射
    unordered_map<int, int> inorderMap;
    for (int i = 0; i < inorder.size(); i++) {
        inorderMap[inorder[i]] = i;
    }
    TreeNode *root = dfs(preorder, inorderMap, 0, 0, inorder.size() - 1);
    return root;
}
build_tree.java
/* 构建二叉树:分治 */
TreeNode dfs(int[] preorder, Map<Integer, Integer> inorderMap, int i, int l, int r) {
    // 子树区间为空时终止
    if (r - l < 0)
        return null;
    // 初始化根节点
    TreeNode root = new TreeNode(preorder[i]);
    // 查询 m ,从而划分左右子树
    int m = inorderMap.get(preorder[i]);
    // 子问题:构建左子树
    root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // 子问题:构建右子树
    root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // 返回根节点
    return root;
}

/* 构建二叉树 */
TreeNode buildTree(int[] preorder, int[] inorder) {
    // 初始化哈希表,存储 inorder 元素到索引的映射
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    TreeNode root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
    return root;
}
build_tree.cs
/* 构建二叉树:分治 */
TreeNode? DFS(int[] preorder, Dictionary<int, int> inorderMap, int i, int l, int r) {
    // 子树区间为空时终止
    if (r - l < 0)
        return null;
    // 初始化根节点
    TreeNode root = new(preorder[i]);
    // 查询 m ,从而划分左右子树
    int m = inorderMap[preorder[i]];
    // 子问题:构建左子树
    root.left = DFS(preorder, inorderMap, i + 1, l, m - 1);
    // 子问题:构建右子树
    root.right = DFS(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // 返回根节点
    return root;
}

/* 构建二叉树 */
TreeNode? BuildTree(int[] preorder, int[] inorder) {
    // 初始化哈希表,存储 inorder 元素到索引的映射
    Dictionary<int, int> inorderMap = [];
    for (int i = 0; i < inorder.Length; i++) {
        inorderMap.TryAdd(inorder[i], i);
    }
    TreeNode? root = DFS(preorder, inorderMap, 0, 0, inorder.Length - 1);
    return root;
}
build_tree.go
/* 构建二叉树:分治 */
func dfsBuildTree(preorder []int, inorderMap map[int]int, i, l, r int) *TreeNode {
    // 子树区间为空时终止
    if r-l < 0 {
        return nil
    }
    // 初始化根节点
    root := NewTreeNode(preorder[i])
    // 查询 m ,从而划分左右子树
    m := inorderMap[preorder[i]]
    // 子问题:构建左子树
    root.Left = dfsBuildTree(preorder, inorderMap, i+1, l, m-1)
    // 子问题:构建右子树
    root.Right = dfsBuildTree(preorder, inorderMap, i+1+m-l, m+1, r)
    // 返回根节点
    return root
}

/* 构建二叉树 */
func buildTree(preorder, inorder []int) *TreeNode {
    // 初始化哈希表,存储 inorder 元素到索引的映射
    inorderMap := make(map[int]int, len(inorder))
    for i := 0; i < len(inorder); i++ {
        inorderMap[inorder[i]] = i
    }

    root := dfsBuildTree(preorder, inorderMap, 0, 0, len(inorder)-1)
    return root
}
build_tree.swift
/* 构建二叉树:分治 */
func dfs(preorder: [Int], inorderMap: [Int: Int], i: Int, l: Int, r: Int) -> TreeNode? {
    // 子树区间为空时终止
    if r - l < 0 {
        return nil
    }
    // 初始化根节点
    let root = TreeNode(x: preorder[i])
    // 查询 m ,从而划分左右子树
    let m = inorderMap[preorder[i]]!
    // 子问题:构建左子树
    root.left = dfs(preorder: preorder, inorderMap: inorderMap, i: i + 1, l: l, r: m - 1)
    // 子问题:构建右子树
    root.right = dfs(preorder: preorder, inorderMap: inorderMap, i: i + 1 + m - l, l: m + 1, r: r)
    // 返回根节点
    return root
}

/* 构建二叉树 */
func buildTree(preorder: [Int], inorder: [Int]) -> TreeNode? {
    // 初始化哈希表,存储 inorder 元素到索引的映射
    let inorderMap = inorder.enumerated().reduce(into: [:]) { $0[$1.element] = $1.offset }
    return dfs(preorder: preorder, inorderMap: inorderMap, i: inorder.startIndex, l: inorder.startIndex, r: inorder.endIndex - 1)
}
build_tree.js
/* 构建二叉树:分治 */
function dfs(preorder, inorderMap, i, l, r) {
    // 子树区间为空时终止
    if (r - l < 0) return null;
    // 初始化根节点
    const root = new TreeNode(preorder[i]);
    // 查询 m ,从而划分左右子树
    const m = inorderMap.get(preorder[i]);
    // 子问题:构建左子树
    root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // 子问题:构建右子树
    root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // 返回根节点
    return root;
}

/* 构建二叉树 */
function buildTree(preorder, inorder) {
    // 初始化哈希表,存储 inorder 元素到索引的映射
    let inorderMap = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }
    const root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
    return root;
}
build_tree.ts
/* 构建二叉树:分治 */
function dfs(
    preorder: number[],
    inorderMap: Map<number, number>,
    i: number,
    l: number,
    r: number
): TreeNode | null {
    // 子树区间为空时终止
    if (r - l < 0) return null;
    // 初始化根节点
    const root: TreeNode = new TreeNode(preorder[i]);
    // 查询 m ,从而划分左右子树
    const m = inorderMap.get(preorder[i]);
    // 子问题:构建左子树
    root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // 子问题:构建右子树
    root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // 返回根节点
    return root;
}

/* 构建二叉树 */
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    // 初始化哈希表,存储 inorder 元素到索引的映射
    let inorderMap = new Map<number, number>();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }
    const root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
    return root;
}
build_tree.dart
/* 构建二叉树:分治 */
TreeNode? dfs(
  List<int> preorder,
  Map<int, int> inorderMap,
  int i,
  int l,
  int r,
) {
  // 子树区间为空时终止
  if (r - l < 0) {
    return null;
  }
  // 初始化根节点
  TreeNode? root = TreeNode(preorder[i]);
  // 查询 m ,从而划分左右子树
  int m = inorderMap[preorder[i]]!;
  // 子问题:构建左子树
  root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
  // 子问题:构建右子树
  root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
  // 返回根节点
  return root;
}

/* 构建二叉树 */
TreeNode? buildTree(List<int> preorder, List<int> inorder) {
  // 初始化哈希表,存储 inorder 元素到索引的映射
  Map<int, int> inorderMap = {};
  for (int i = 0; i < inorder.length; i++) {
    inorderMap[inorder[i]] = i;
  }
  TreeNode? root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
  return root;
}
build_tree.rs
/* 构建二叉树:分治 */
fn dfs(
    preorder: &[i32],
    inorder_map: &HashMap<i32, i32>,
    i: i32,
    l: i32,
    r: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    // 子树区间为空时终止
    if r - l < 0 {
        return None;
    }
    // 初始化根节点
    let root = TreeNode::new(preorder[i as usize]);
    // 查询 m ,从而划分左右子树
    let m = inorder_map.get(&preorder[i as usize]).unwrap();
    // 子问题:构建左子树
    root.borrow_mut().left = dfs(preorder, inorder_map, i + 1, l, m - 1);
    // 子问题:构建右子树
    root.borrow_mut().right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r);
    // 返回根节点
    Some(root)
}

/* 构建二叉树 */
fn build_tree(preorder: &[i32], inorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
    // 初始化哈希表,存储 inorder 元素到索引的映射
    let mut inorder_map: HashMap<i32, i32> = HashMap::new();
    for i in 0..inorder.len() {
        inorder_map.insert(inorder[i], i as i32);
    }
    let root = dfs(preorder, &inorder_map, 0, 0, inorder.len() as i32 - 1);
    root
}
build_tree.c
/* 构建二叉树:分治 */
TreeNode *dfs(int *preorder, int *inorderMap, int i, int l, int r, int size) {
    // 子树区间为空时终止
    if (r - l < 0)
        return NULL;
    // 初始化根节点
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = preorder[i];
    root->left = NULL;
    root->right = NULL;
    // 查询 m ,从而划分左右子树
    int m = inorderMap[preorder[i]];
    // 子问题:构建左子树
    root->left = dfs(preorder, inorderMap, i + 1, l, m - 1, size);
    // 子问题:构建右子树
    root->right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r, size);
    // 返回根节点
    return root;
}

/* 构建二叉树 */
TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize) {
    // 初始化哈希表,存储 inorder 元素到索引的映射
    int *inorderMap = (int *)malloc(sizeof(int) * MAX_SIZE);
    for (int i = 0; i < inorderSize; i++) {
        inorderMap[inorder[i]] = i;
    }
    TreeNode *root = dfs(preorder, inorderMap, 0, 0, inorderSize - 1, inorderSize);
    free(inorderMap);
    return root;
}
build_tree.kt
/* 构建二叉树:分治 */
fun dfs(
    preorder: IntArray,
    inorderMap: Map<Int?, Int?>,
    i: Int,
    l: Int,
    r: Int
): TreeNode? {
    // 子树区间为空时终止
    if (r - l < 0) return null
    // 初始化根节点
    val root = TreeNode(preorder[i])
    // 查询 m ,从而划分左右子树
    val m = inorderMap[preorder[i]]!!
    // 子问题:构建左子树
    root.left = dfs(preorder, inorderMap, i + 1, l, m - 1)
    // 子问题:构建右子树
    root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r)
    // 返回根节点
    return root
}

/* 构建二叉树 */
fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
    // 初始化哈希表,存储 inorder 元素到索引的映射
    val inorderMap = HashMap<Int?, Int?>()
    for (i in inorder.indices) {
        inorderMap[inorder[i]] = i
    }
    val root = dfs(preorder, inorderMap, 0, 0, inorder.size - 1)
    return root
}
build_tree.rb
### 构建二叉树:分治 ###
def dfs(preorder, inorder_map, i, l, r)
  # 子树区间为空时终止
  return if r - l < 0

  # 初始化根节点
  root = TreeNode.new(preorder[i])
  # 查询 m ,从而划分左右子树
  m = inorder_map[preorder[i]]
  # 子问题:构建左子树
  root.left = dfs(preorder, inorder_map, i + 1, l, m - 1)
  # 子问题:构建右子树
  root.right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r)

  # 返回根节点
  root
end

### 构建二叉树 ###
def build_tree(preorder, inorder)
  # 初始化哈希表,存储 inorder 元素到索引的映射
  inorder_map = {}
  inorder.each_with_index { |val, i| inorder_map[val] = i }
  dfs(preorder, inorder_map, 0, 0, inorder.length - 1)
end
可视化运行

图 12-8 展示了构建二叉树的递归过程,各个节点是在向下“递”的过程中建立的,而各条边(引用)是在向上“归”的过程中建立的。

图 12-8   构建二叉树的递归过程

图解 12-8:递归构树:向下创建节点,返回时连接子树

向下递进时依次创建节点 3、9、2、1、7,向上回溯返回时才将子树连接到父节点,最终建成五节点树。

输入为前序遍历 preorder = [3, 9, 2, 1, 7] 与中序遍历 inorder = [9, 3, 1, 2, 7],节点值互不重复。

每个递归子问题先从前序有效段首元素初始化当前根节点(向下“递”时创建节点),再按中序位置划分并递归构建左、右子树;当子调用返回子树根节点后,父调用才将其赋给当前根的 left 或 right 引用(向上“归”时建立连边)。空区间调用直接返回 None。

九幅画面展示创建节点或接回子树的时刻;空区间返回 None 的调用未单独拆成画面。每步的“构树第 N 步”表列出此时全部已创建节点及引用。“未连接”表示相应子树尚待构建或返回连接;“无”表示该节点确实没有这个子节点。

固定遍历输入
索引前序值中序值
039
193
221
312
477
  1. 创建根节点 3

    进入顶层调用 i = 0、中序区间 [0, 4],由前序首项创建根 3。在中序索引 1 处找到 3,左子树为 [9],右子树的中序为 [1, 2, 7]、前序为 [2, 1, 7]。当前只创建了根 3,没有父子边;接下来先递归构建左子树。

    构树第 1 步:创建根节点 3 后的节点及引用
    节点左子节点右子节点
    3未连接未连接
  2. 创建叶节点 9

    进入左子问题 i = 1、中序区间 [0, 0],创建节点 9。它的左右中序子区间均为空,对应空子树调用返回 None,所以 9 是叶节点。构建节点 9 的调用尚未把它返回给根 3,当前两个节点之间没有连边。

    构树第 2 步:创建叶节点 9 后的节点及引用
    节点左子节点右子节点
    3未连接未连接
    9无无
  3. 连接左子树 9

    构建节点 9 的调用将它返回给根 3,父调用执行 3.left = 9,建立第一条边。根 3 的右子树尚待构建,接下来转向右子问题。

    构树第 3 步:连接左子树 9 后的节点及引用
    节点左子节点右子节点
    39未连接
    9无无
  4. 创建右子树根 2

    进入右子问题 i = 2、中序区间 [2, 4],从有效前序段 [2, 1, 7] 的首项创建节点 2。节点 2 在中序中的索引 m = 3,其左子问题为 [1]、右子问题为 [7]。当前 3.left = 9 保持不变;2 的两侧尚未连接,以 2 为根的调用尚未返回给 3,因此 3 与 2 之间没有连边。

    构树第 4 步:创建右子树根 2 后的节点及引用
    节点左子节点右子节点
    39未连接
    9无无
    2未连接未连接
  5. 创建叶节点 1

    进入节点 2 的左子问题 i = 3、中序区间 [2, 2],创建叶节点 1。它两侧的中序子区间为空,但构建节点 1 的调用尚未把它返回给节点 2。当前已创建四个节点,只建立了 3.left = 9;1 未接到 2,2 也未接回 3。

    构树第 5 步:创建叶节点 1 后的节点及引用
    节点左子节点右子节点
    39未连接
    9无无
    2未连接未连接
    1无无
  6. 连接节点 2 的左子树

    构建节点 1 的调用返回给节点 2,父调用执行 2.left = 1。当前已建立 3.left = 9 和 2.left = 1;节点 2 的右子问题 [7] 尚待构建,2 仍未返回并连接到 3。

    构树第 6 步:连接节点 2 的左子树后的节点及引用
    节点左子节点右子节点
    39未连接
    9无无
    21未连接
    1无无
  7. 创建叶节点 7

    进入节点 2 的右子问题 i = 4、中序区间 [4, 4],创建最后一个叶节点 7。五个节点均已创建;当前已有 3.left = 9 和 2.left = 1,而 2.right、3.right 尚未连接。构建节点 7 的调用即将把它返回给节点 2。

    构树第 7 步:创建叶节点 7 后的节点及引用
    节点左子节点右子节点
    39未连接
    9无无
    21未连接
    1无无
    7无无
  8. 连接节点 2 的右子树

    构建节点 7 的调用返回给节点 2,父调用执行 2.right = 7。当前三条边为 3.left = 9、2.left = 1、2.right = 7;以 2 为根的子树已完整,准备返回给根 3,3 与 2 之间尚未连边。

    构树第 8 步:连接节点 2 的右子树后的节点及引用
    节点左子节点右子节点
    39未连接
    9无无
    217
    1无无
    7无无
  9. 连接完整右子树

    以 2 为根的右子树返回给顶层调用,执行 3.right = 2,建立最后一条边。当前 3 左接 9、右接 2,2 左接 1、右接 7;9、1、7 是叶节点。四条父子边全部建立,顶层函数返回根 3,构建完成。

    构树第 9 步:连接完整右子树后的节点及引用
    节点左子节点右子节点
    392
    9无无
    217
    1无无
    7无无

建成树的前序遍历为 [3, 9, 2, 1, 7],中序遍历为 [9, 3, 1, 2, 7],与输入一致。

每个递归函数内的前序遍历 preorder 和中序遍历 inorder 的划分结果如图 12-9 所示。

图 12-9   每个递归函数中的划分结果

图解 12-9:逐个子问题查看前序与中序的划分

根 3 拆出左叶 9 与以 2 为根的右子树,节点 2 再拆出左右叶 1、7;各节点旁标出对应的遍历有效区间。

输入为前序遍历 preorder = [3, 9, 2, 1, 7] 与中序遍历 inorder = [9, 3, 1, 2, 7],节点值互不重复。

重建出的二叉树以 3 为根,左子节点为 9,右子节点为 2;节点 2 的左右子节点分别为 1 和 7;节点 9、1、7 均为叶节点。

画面在树的五个节点旁各画出一组完整长度的 preorder 和 inorder 数组,仅将属于当前递归子问题的区间着色,其余无关位置置为浅灰色。在每个子问题中,青色代表当前子树的根节点,蓝色代表其左子树区间,紫色代表其右子树区间。

浅灰格仍是原数组的一部分,只是不属于当前子问题;叶节点的有效序列只剩根,两侧子树段均为空。下表明确写出各有效序列中的根、左段与右段。表中“左右子树根”按图中的父子边归纳。

每个非空递归子问题的有效序列
当前根前序有效部分:根、左、右中序有效部分:左、根、右左右子树根
3根 3;左 [9];右 [2, 1, 7]左 [9];根 3;右 [1, 2, 7]左9,右2
9根 9;左空;右空左空;根 9;右空均为空
2根 2;左 [1];右 [7]左 [1];根 2;右 [7]左1,右7
1根 1;左空;右空左空;根 1;右空均为空
7根 7;左空;右空左空;根 7;右空均为空

同一个节点值在不同递归子问题的数组中承担不同的颜色角色:例如元素 2 在根 3 的顶层数组中属于紫色右子树区间,而在以 2 自身为根的子问题数组中则变为青色根元素。图中树的五个圆形节点本身均为绿色。

各子问题重复同一规则:前序定根、中序划分左右范围;叶节点两侧的空区间返回空引用。

设树的节点数量为 \(n\) ,初始化每一个节点(执行一个递归函数 dfs() )使用 \(O(1)\) 时间。因此总体时间复杂度为 \(O(n)\) 。

哈希表存储 inorder 元素到索引的映射,空间复杂度为 \(O(n)\) 。在最差情况下,即二叉树退化为链表时,递归深度达到 \(n\) ,使用 \(O(n)\) 的栈帧空间。因此总体空间复杂度为 \(O(n)\) 。

欢迎在评论区留下你的见解、问题或建议