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)|\) 表示右子树的节点数量

输入约束

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

遍历公理

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

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

2. 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)|\)，则：

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

证明：

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

引理 1（左孩子判定）

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

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

则 \(v\) 必然是 \(u\) 的左孩子。

证明：

1. 由条件 2 和公理 A2，\(v \in T_L(u)\)（\(v\) 在 \(u\) 的左子树中）。
2. 由引理 0，\(T_L(u)\) 的所有节点的 \(pre\) 值都落在区间 \([pre(u)+1, pre(u)+L]\) 内，其中 \(L=|T_L(u)|\)。
3. 条件 1 说明 \(pre(v)=pre(u)+1\)，是该区间的最小索引，即左子树中第一个被前序访问的节点。
4. 由公理 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\)，若满足：

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

则 \(v\) 必然是 \(u\) 的右孩子。

证明：

1. 由条件 2 和公理 A2，\(v \in T_R(u)\)（\(v\) 在 \(u\) 的右子树中）。
2. 由引理 0，\(T_R(u)\) 的所有节点的 \(pre\) 值都落在区间 \([pre(u)+L+1, pre(u)+L+R]\) 内，其中 \(L=|T_L(u)|\)。
3. 条件 1、3 说明 \(pre(v)\) 是该区间的最小索引，即右子树中第一个被前序访问的节点。
4. 由公理 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 条性质恒成立：

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

不变量证明

初始阶段

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

证明：

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

保持阶段

情况1

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

1. 分支条件的数学映射：
   由循环前不变量 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)\)。

2. 用引理 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 的构造操作正确。

3. 证明不变量保持：

   • 栈性质：新节点 \(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]）

1. 内层循环的数学意义：
   内层循环的条件为「栈顶值等于 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. 用引理2证明分支操作的正确性：
   \(last\_pop\) 和 \(v\) 完全满足引理 2 的3个条件，因此 \(v\) 必然是 \(last\_pop\) 的右孩子，分支 2 的构造操作正确。

3. 证明不变量保持：

   • 栈性质：新节点 \(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，成立。

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

终止阶段

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

1. 由不变量 3，已构造节点的 pre 值覆盖 [0, n-1]，即二叉树的所有节点均已构造完成。
2. 由不变量 2，所有节点均已标记为完成，idx 最终等于 n，所有节点的子树均已完全构造。
3. 由不变量 3，所有父子关系均符合前序、中序遍历的公理，因此构造的树的前序遍历为preorder，中序遍历为 inorder。
4. 由前提 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 --