LeetCode 105 从前序与中序遍历构造二叉树迭代算法原理 + 完整证明

最近为了找新工作机会开始刷 LeetCode，由于这道题迭代解法的官方讲解比较抽象，难以理解，算法的正确性也不够直观，且没有给出证明。即便照着把算法背下来，心里依然不踏实。我个人刷题的习惯是：遇到正确性不显然的算法，一定要证明其正确性。我发现，这可以极大加深对算法的理解和记忆，就算后续忘记算法，临场也能自行推演出来；而单纯死记硬背的内容，一旦忘记就很难再回想。

当然，这个算法本身非常精妙且复杂，除非注意力惊人，否则在从未接触过的情况下，很难独立推导出来（对我来说）。因此我们不去探究该算法是如何被发现的，而是假定已知算法，仅证明其正确性。

以下证明由人类提供证明思路，AI 进行形式化描述，最后由人类审核所有引理、定理及证明过程的正确性。

题目描述

此处省略，详见 105. 从前序与中序遍历序列构造二叉树。

符号定义

$n$：二叉树节点总数，满足 $n \geq 1$
$T$：无重复节点值的二叉树
$preorder[0..n-1]$：$T$ 的前序遍历序列，$pre(u)$ 表示节点 $u$ 在该序列中的唯一索引
$inorder[0..n-1]$：$T$ 的中序遍历序列，$in(u)$ 表示节点 $u$ 在该序列中的唯一索引
$T_L(u)$：节点 $u$ 的左子树（含所有后代），$|T_L(u)|$ 表示左子树的节点数量
$T_R(u)$：节点 $u$ 的右子树（含所有后代），$|T_R(u)|$ 表示右子树的节点数量

输入约束

P1（无重复）：$preorder$ 和 $inorder$ 元素无重复，长度均为 $n$
P2（一致性）：$preorder$ 和 $inorder$ 的元素集合完全相等
P3（合法性）：存在唯一的二叉树 $T$，其前序遍历为 $preorder$，中序遍历为 $inorder$

遍历公理

这是根据二叉树遍历定义的固有数学性质，对 $T$ 中任意节点 $u$，以下性质恒成立：

A1（前序规则）：前序遍历顺序为「根→左子树→右子树」，即：
$$pre(u) < pre(v), \forall v \in T_L(u) \cup T_R(u)$$
且 $T_L(u)$ 所有节点的 $pre$ 值，严格小于 $T_R(u)$ 所有节点的 $pre$ 值。
A2（中序规则）：中序遍历顺序为「左子树→根→右子树」，即：
$$in(v) < in(u), \forall v \in T_L(u); \quad in(v) > in(u), \forall v \in T_R(u)$$

基础引理

引理 0（子树序列连续性）

对 $T$ 中任意节点 $u$，设 $L=|T_L(u)|, R=|T_R(u)|$，则：

前序序列中，$pre(u)+1$ 到 $pre(u)+L$ 恰好是 $T_L(u)$ 的所有节点；$pre(u)+L+1$ 到 $pre(u)+L+R$ 恰好是 $T_R(u)$ 的所有节点。
中序序列中，$in(u)-L$ 到 $in(u)-1$ 恰好是 $T_L(u)$ 的所有节点；$in(u)+1$ 到 $in(u)+R$ 恰好是 $T_R(u)$ 的所有节点。

证明：

由公理 A1，前序遍历先访问根 $u$，再连续访问完整个左子树，再连续访问完整个右子树，因此左、右子树的节点在 preorder 中必然是连续的两段，且左段在前。
由公理 A2，中序遍历先连续访问完整个左子树，再访问根 $u$，再连续访问完整个右子树，因此左、右子树的节点在 inorder 中必然是连续的两段，且左段在根左侧，右段在根右侧。

引理 1（左孩子判定）

对 $T$ 中任意两个节点 $u, v$，若满足：

$pre(v) = pre(u) + 1$（前序序列中连续，$u$ 在前）
$in(v) < in(u)$（$v$ 在中序序列中位于 $u$ 前面）

则 $v$ 必然是 $u$ 的左孩子。

证明：

由条件 2 和公理 A2，$v \in T_L(u)$（$v$ 在 $u$ 的左子树中）。
由引理 0，$T_L(u)$ 的所有节点的 $pre$ 值都落在区间 $[pre(u)+1, pre(u)+L]$ 内，其中 $L=|T_L(u)|$。
条件 1 说明 $pre(v)=pre(u)+1$，是该区间的最小索引，即左子树中第一个被前序访问的节点。
由公理 A1，左子树中第一个被访问的节点，必然是左子树的根，也就是 $u$ 的左孩子。

推论

若 $pre(v) = pre(u) + 1$，且 $u$ 的左子树存在，则 $v$ 是 $u$ 的左孩子。

证明：

由于 $u$ 的左子树存在，根据引理 0，$v$ 必然在 $u$ 的左子树中，再根据公理 A2，必有 $in(v) < in(u)$，满足引理 1 的条件，因此 $v$ 是 $u$ 的左孩子。

引理 2（右孩子判定）

对 $T$ 中任意两个节点 $u, v$，若满足：

$T_L(u)$ 的所有节点的 $pre$ 值都严格小于 $pre(v)$（$u$ 的左子树已全部被前序访问）
$in(v) > in(u)$（$v$ 在中序序列中位于 $u$ 后面）
$pre(v)$ 是满足条件 1、2 的最小 $pre$ 值（$v$ 是 $u$ 的右子树中第一个被前序访问的节点）

则 $v$ 必然是 $u$ 的右孩子。

证明：

由条件 2 和公理 A2，$v \in T_R(u)$（$v$ 在 $u$ 的右子树中）。
由引理 0，$T_R(u)$ 的所有节点的 $pre$ 值都落在区间 $[pre(u)+L+1, pre(u)+L+R]$ 内，其中 $L=|T_L(u)|$。
条件 1、3 说明 $pre(v)$ 是该区间的最小索引，即右子树中第一个被前序访问的节点。
由公理 A1，右子树中第一个被访问的节点，必然是右子树的根，也就是 $u$ 的右孩子。

算法形式化描述

输入：preorder[0..n-1], inorder[0..n-1]
输出：二叉树T的根节点root

1. 若n=0，返回nullptr
2. 初始化：
   a. root = 新节点(preorder[0])
   b. stk = 空栈，stk.push(root)
   c. idx = 0（中序序列指针）
   d. i = 1（前序序列遍历指针）
3. 外层循环：当i < n时：
   a. curr_val = preorder[i]，对应节点v，pre(v)=i
   b. top_node = stk.top()，对应节点u，pre(u)=i-1
   c. 分支1：若 top_node.val ≠ inorder[idx]
       i. 构造 top_node.left = 新节点(curr_val)
       ii. stk.push(top_node.left)
   d. 分支2：否则（top_node.val == inorder[idx]）
       i. last_pop = nullptr
       ii. 内层循环：当stk非空 且 stk.top().val == inorder[idx]
           - last_pop = stk.top()
           - stk.pop()
           - idx = idx + 1
       iii. 构造 last_pop.right = 新节点(curr_val)
       iv. stk.push(last_pop.right)
   e. i = i + 1
4. 返回root

循环不变量

在外层循环每次开始时（即 i 更新后，进入循环体前），以下 3 条性质恒成立：

栈性质：
- 栈中节点按前序访问顺序排列，栈底为 root，栈顶为当前已构造节点中 pre 值最大的节点（即 pre = i-1的节点）。
- 栈中所有节点的右孩子均未被构造。
中序指针性质：
- $inorder[0..idx-1]$ 对应的所有节点，其左子树、自身均已构造完成，不会再被修改。
- 栈中所有节点的 $in$ 值均 $\geq idx$。
- 令 $w_0 = inorder[idx]$，$w_0$ 不在已完成区间（即未被完全处理），$w_0$ 的左子树全部属于已完成区间 $inorder[0..idx-1]$。
构造正确性：
- 已构造节点的 pre 值恰好覆盖 $[0, i-1]$，无遗漏、无多余。
- 已构造的所有父子关系，均符合公理 A1、A2。

不变量证明

初始阶段

即 i=1，外层循环第一次开始前，不变量全部成立。

证明：

栈性质：栈中仅含 root，pre(root) = 0 = i-1，栈顶为 pre 值最大的节点；root 的右孩子未构造，成立。
中序指针性质：idx=0，$inorder[0..-1]$ 为空集，无已完成节点；栈中 root 的 in 值 ≥0，成立；$w_0 = inorder[0]$，已完成区间 inorder[0..-1] = ∅,所以 $w_0$ 不在已完成区间，$w_0$ 的左子树必然是 ∅，属于已完成区间
构造正确性：已构造节点仅 root，pre 值覆盖 [0,0] = [0,i-1]；无非法父子关系，成立。

保持阶段

情况1

执行分支 1（top_node.val ≠ inorder[idx]）

分支条件的数学映射：
由循环前不变量 2，栈中所有节点的 in 值 ≥idx，因此 $in(top\_node) ≥ idx$。结合分支条件 $top\_node.val ≠ inorder[idx]$，得 $in(top\_node) > idx$。由不变量 2，$inorder[idx]$ 对应的节点的左子树已全部完成，因此该节点必然在 $top\_node$ 的左子树中，即 $top\_node$ 的左子树非空，存在节点 $w$ 满足 $in(w) < in(top\_node)$。
用引理 1 证明分支操作的正确性：
当前节点 $v$ 的 $pre(v)=i$，$top\_node$ 的 $pre(top\_node)=i-1$，满足 $pre(v)=pre(top\_node)+1$；而 $top\_node$ 的左子树非空，根据引理 1 的推论，$v$ 必然是 $top\_node$ 的左孩子，分支 1 的构造操作正确。
证明不变量保持：
- 栈性质：新节点 $v$ 的 pre 值为 i，是当前最大 pre 值，入栈后栈顶仍为 pre 最大的节点；$v$ 的右孩子未构造，栈中其他节点的右孩子仍未构造，成立。
- 中序指针性质：idx 未变化，已完成节点集合未变化；由于 $v$ 是新处理的节点，所以$in(v) \geq idx$（因为根据 循环前不变量 2，inorder[0..idx-1] 是已经完全处理完毕的节点，而新处理节点不属于这个集合），所以栈中所有节点的 in 值仍 ≥idx，成立。
- 构造正确性：已构造节点的 pre 值新增 i，覆盖 [0,i]；循环后 i 自增为 i+1，因此覆盖 [0,(i+1)−1]；父子关系符合引理 2，满足公理 A1、A2，成立。

情况2

执行分支2（top_node.val == inorder[idx]）

内层循环的数学意义：
内层循环的条件为「栈顶值等于 inorder[idx]」，每次循环弹出栈顶节点、idx 自增1。由循环前不变量 2，栈顶节点的 in 值=idx，说明该节点的左子树已全部完成，将其标记为已完成节点，idx 自增对应中序遍历的推进。循环结束后，$last\_pop$ 是最后一个弹出的节点，满足：
- $last\_pop$ 的左子树已全部完成（对应引理 2 的条件 1）：内层循环迭代时，考虑第一次循环，弹出节点为 $first\_pop$，循环条件保证 $in(first\_pop) = idx$，根据中序公理，$first\_pop$ 左子树中任意节点 $x$ 满足 $in(x) < in(first\_pop) = idx$，结合不变量 2，$inorder[0..idx-1]$ 内所有节点均已完全构造完成，也就是说 $first\_pop$ 的左子树节点 $x$ 全部包含于已完成区间，即左子树已全部完成，而 $first\_pop$ 是栈中弹出节点，本身已经构造完成，因此 $in(first\_pop) = idx$ 对应节点可加入 $inorder[0..idx-1]$ 中，拓展为 $inorder[0..idx]$ 为已完成节点。依次类推，直到最后弹出节点 $last\_pop$，其左子树已全部完成，设此时中序索引更新为 $idx_1$，那么 $inorder[0..idx_1-1]$ 都为已完成节点，这个结论也说明，内存循环结束后，不变量 2 中该性质依然成立：$inorder[0..idx-1]$ 对应的所有节点，其左子树、自身均已完全构造完成，不会再被修改。
- $in(v) > in(last\_pop)$（对应引理2的条件2）：内层循环结束后，中序索引更新为 $idx_1$，满足 $in(last\_pop) = idx_1-1$；根据上面的分析，$inorder[0..idx_1-1]$ 内节点均已构造完成，而待构造节点 $v$ 未被构造，故 $in(v) \notin [0,idx_1-1]$，即 $in(v) \ge idx_1$，因此 $in(v) \ge idx_1 > idx_1-1 = in(last\_pop)$，得 $in(v) > in(last\_pop)$。
- 当前节点 $v$ 的 $pre(v)=i$，是大于 $pre(last\_pop)$ 的最小 pre 值（对应引理 2 的条件 3）：由不变量 3，$last\_pop$ 为已构造节点，故 $pre(last\_pop) \in [0,i-1]$，即 $pre(v)=i > pre(last\_pop)$；假设存在比 $i$ 更小的 $pre'$ 满足引理 2 的条件，有 $pre(last\_pop) < pre' < i$，由不变量 3 可知其对应节点为已构造节点，而栈中节点右孩子均未构造，$last\_pop$ 无已构造的右子树节点，故不存在满足条件的 $pre'$，因此 $pre(v)=i$ 是大于 $pre(last\_pop)$ 的最小 pre 值。
用引理2证明分支操作的正确性：
$last\_pop$ 和 $v$ 完全满足引理 2 的3个条件，因此 $v$ 必然是 $last\_pop$ 的右孩子，分支 2 的构造操作正确。
证明不变量保持：
- 栈性质：新节点 $v$ 的 pre 值为 i，是当前最大 pre 值，入栈后栈顶仍为 pre 最大的节点；$v$ 的右孩子未构造，栈中剩余节点的右孩子仍未构造，成立。
- 中序指针性质：idx 自增到新值后，根据之前分析，inorder[0..idx−1] 对应的所有节点左子树与自身均已完全构造完成且不再修改，满足第一条；栈中原剩余节点始终满足 in 值 ≥idx，新入栈节点 $v$ 未在已完成区间内，故 $in(v)≥idx$，因此栈中所有节点 in 值均 ≥idx，满足第二条；令 $w_0=inorder[idx]$，由内层循环终止条件与栈不变量，$w_0$ 不在已完成区间内，且由中序公理，$w_0$ 左子树任意节点 $in(x)<idx$，全部属于已完成区间，满足第三条，中序指针性质全部保持成立。
- 构造正确性：已构造节点的pre值新增 i，覆盖 [0,i]；循环后 i 自增为 i+1，因此覆盖 [0, (i+1)-1]；父子关系符合引理 2，满足公理 A1、A2，成立。

无论执行哪个分支，循环后不变量全部保持成立。

终止阶段

循环结束时，不变量仍成立，由此推导算法正确性：

由不变量 3，已构造节点的 pre 值覆盖 [0, n-1]，即二叉树的所有节点均已构造完成。
由不变量 2，所有节点均已标记为完成，idx 最终等于 n，所有节点的子树均已完全构造。
由不变量 3，所有父子关系均符合前序、中序遍历的公理，因此构造的树的前序遍历为preorder，中序遍历为 inorder。
由前提 P3，前序+中序序列唯一确定一棵二叉树，因此构造的树就是题目要求的正确二叉树。

结论

该算法对所有满足题目前提的合法输入，均能正确构造出对应的二叉树，算法完全正确。

代码实现

理解上述证明后，算法的循环逻辑以及循环过程中的各类分支条件便会十分清晰，下面给出一个 Rust 语言实现的示例：

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;

impl Solution {
    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        if preorder.is_empty() {
            return None;
        }

        let root = Rc::new(RefCell::new(TreeNode::new(preorder[0])));
        let mut stack = VecDeque::new();
        stack.push_back(root.clone());

        let mut idx = 0;
        for &val in &preorder[1..] {
            let top_val = stack.back().unwrap().borrow().val;

            if top_val != inorder[idx] {
                let new_node = Rc::new(RefCell::new(TreeNode::new(val)));
                stack.back().unwrap().borrow_mut().left = Some(new_node.clone());
                stack.push_back(new_node);
            } else {
                let mut last_pop = None;
                while let Some(node) = stack.back() {
                    let curr_val = node.borrow().val;
                    if curr_val == inorder[idx] {
                        last_pop = stack.pop_back();
                        idx += 1;
                    } else {
                        break;
                    }
                }

                let new_node = Rc::new(RefCell::new(TreeNode::new(val)));
                last_pop.as_ref().unwrap().borrow_mut().right = Some(new_node.clone());
                stack.push_back(new_node);
            }
        }

        Some(root)
    }
}

-- EOF --

推荐订阅源

追梦人物的博客