9.4　树题递归套路：返回值该是什么

学习目标：学完本节，你能

• 判断一道树题该用自顶向下还是自底向上；
• 根据题目要求设计递归函数的返回值；
• 独立解决最大深度、判断平衡、最近公共祖先这三类经典题。

先修：9.2、9.3（全部遍历方式）。 固定术语：自顶向下、自底向上、返回值语义、回溯。 环境与版本：.NET 8 / C# 12。 预计阅读：34 分钟。

一、直觉：递归函数是一个"黑盒"

写树题时最常见的困惑是：

"我知道要用递归，但递归函数该返回什么？"

解决方法是把递归函数当成一个"黑盒"来设计：

不要去想它内部怎么实现，只问两个问题：

1. 它接收什么？（参数的含义）
2. 它返回什么？（返回值的含义）

把这两个问题回答清楚，代码自然就出来了。

以"求最大深度"为例：

static int MaxDepth(TreeNode? node)
    => node == null ? 0 : 1 + Math.Max(MaxDepth(node.Left), MaxDepth(node.Right));

黑盒设计：

• 接收：一个节点
• 返回：以这个节点为根的子树的最大深度
• 基准情形：空节点返回 0
• 递推：自己的深度 = 1 + max(左子树深度, 右子树深度)

注意"返回值语义"里最重要的一点：返回值描述的是"以当前节点为根的整棵子树"，而不是"从根到当前节点的路径"。

这个方向搞反了，是树题写不出来的头号原因。

二、两大套路：自顶向下 vs 自底向上

自底向上（后序）：先要子树的结果，再算自己

特征：要算当前节点，必须先知道子树的结果。

典型题目：最大深度、节点数、判断平衡、最近公共祖先。

       ┌─────────────────────────────┐
       │  先递归求左子树的结果          │
       │  再递归求右子树的结果          │
       │  用两个结果算出自己的结果       │
       └─────────────────────────────┘

代码形态：

int Solve(TreeNode? node)
{
    if (node == null) return 基准值;

    var left = Solve(node.Left);      // 先要左子树的结果
    var right = Solve(node.Right);    // 再要右子树的结果
    return 用(left, right) 算出的自己的结果;   // ← "访问自己"在最后，就是后序
}

自顶向下（前序）：带着状态往下传

特征：当前节点的答案依赖于"从根一路传下来的状态"，而不是子树的结果。

典型题目：根到叶子的路径、判断是否存在某条路径、给每个节点标注深度。

       ┌─────────────────────────────┐
       │  用传进来的状态处理自己        │
       │  把新状态传给左孩子            │
       │  把新状态传给右孩子            │
       └─────────────────────────────┘

代码形态：

void Solve(TreeNode? node, 状态 state)
{
    if (node == null) return;

    处理(node, state);                 // ← "访问自己"在最前，就是前序
    Solve(node.Left, 更新(state, node));
    Solve(node.Right, 更新(state, node));
}

判断方法（一句话）：

问自己："要算当前节点的答案，需不需要先知道左右子树的结果？"

• 需要 → 自底向上（后序）
• 不需要 → 自顶向下（前序）

三、经典题一：最大深度（自底向上）

黑盒设计：

static int MaxDepth(TreeNode? node)
    => node == null ? 0 : 1 + Math.Max(MaxDepth(node.Left), MaxDepth(node.Right));

实测：平衡树返回 3，链状树返回 4 ✓

为什么是自底向上？ 因为"我的深度"必须先知道"左右子树的深度" —— 依赖子树的结果。

四、经典题二：判断平衡（自底向上 + 提前失败）

问题：判断一棵树是否平衡（每个节点的左右子树高度差不超过 1）。

朴素解法（自顶向下，$O(n^2)$）：

static bool IsBalancedNaive(TreeNode? node)
{
    if (node == null) return true;
    int left = Height(node.Left);          // 每个节点都重新算一次高度！
    int right = Height(node.Right);
    if (Math.Abs(left - right) > 1) return false;
    return IsBalancedNaive(node.Left) && IsBalancedNaive(node.Right);
}

问题在哪？

Height() 会遍历整棵子树，而 IsBalancedNaive 对每个节点都调用两次 Height。

总代价 = $\sum_{\text{每个节点}} (\text{该节点的子树大小})$，每个节点都被重复计算了很多次。

优化解法（自底向上，$O(n)$）：

关键技巧：用返回值"顺便"传递高度，同时用 -1 表示"已经不平衡了"。

/// <summary>
/// 判断是否为平衡二叉树。
/// 技巧：用返回 -1 表示「已经不平衡了」，这样只需要遍历一次。
/// </summary>
static int CheckBalance(TreeNode? node)
{
    if (node == null) return 0;

    int left = CheckBalance(node.Left);
    if (left == -1) return -1;                  // 左子树已经不平衡，不用再算了

    int right = CheckBalance(node.Right);
    if (right == -1) return -1;                 // 右子树不平衡

    if (Math.Abs(left - right) > 1) return -1;  // 自己不平衡

    return 1 + Math.Max(left, right);           // 返回高度
}

static bool IsBalanced(TreeNode? root) => CheckBalance(root) != -1;

实测：平衡树返回 True，链状树返回 False ✓

这个设计的精妙之处：

用一个返回值同时表达了两件事。 这是树题里非常常见的技巧 —— 当"结果"和"是否有效"需要一起返回时，用一个特殊值表示"无效"。

if (left == -1) return -1; 这两行是"提前失败" —— 一旦发现不平衡，就不再往下算了，直接把这个坏消息一路往上传。

性能对比实测：

  场景 A：8000 个节点的【链状树】（处处不平衡，根节点就能发现）
    自底向上:    0.166 ms
    自顶向下:    0.072 ms
    结果一致: True
    -> 注意：这里【朴素版反而更快】！因为它一进根节点就算出左右子树高度差极大，
       立刻返回 false，根本没往下递归。

  场景 B：8,191 个节点的【完美平衡树】（处处平衡，必须走完全程）
    自底向上:    0.030 ms
    自顶向下:    0.282 ms
    结果一致: True，自底向上快 9.3 倍

这两个场景给出了一个反直觉但重要的结论：

朴素版的最坏情况不是"链状树"（它会提前失败），而是"平衡树"。

因为在链状树上：根节点的左右子树高度一个是 7999、一个是 $-1$（空），高度差巨大 —— 第一次检查就 return false 了，根本不会往下递归。

而在平衡树上：每个节点都是平衡的，必须一路走到最深处，而且在走的路上，每个节点都要重新算一遍子树高度。

总代价 $= \sum (\text{子树大小}) \approx n \log_2 n$，所以是 $O(n \log n)$，不是 $O(n^2)$。

（很多教材粗略地说它是 $O(n^2)$，那是把"每次 Height 是 $O(n)$、调用 $n$ 次"直接相乘了 —— 但"是否真的调用 $n$ 次"取决于树会不会提前失败。）

这个例子的教训是："最坏情况"要靠实际推演，不能靠粗略的乘法估算。

而且 —— 用错了测试数据，你会得出完全相反的结论。如果我只测链状树，就会得出"自顶向下更快"的错误结论。

五、经典题三：最近公共祖先（LCA）

问题：给定一棵二叉树和两个节点 p、q，找出它们的最近公共祖先（最低的、同时是两者祖先的节点）。

测试树：

                3
               /   \
              5     1
             / \   / \
            6   2 0   8
               / \
              7   4

黑盒设计（这是本节最难的一个）：

static TreeNode? LowestCommonAncestor(TreeNode? root, TreeNode p, TreeNode q)
{
    if (root == null) return null;
    if (root == p || root == q) return root;          // 找到了其中一个

    var left = LowestCommonAncestor(root.Left, p, q);
    var right = LowestCommonAncestor(root.Right, p, q);

    // 左右都找到了 -> 说明 p 和 q 分居两侧，root 就是 LCA
    if (left != null && right != null) return root;

    // 只有一边找到 -> 说明两个目标都在那一边（或者只找到了一个）
    return left ?? right;
}

实测结果：

    LCA(5, 1) = 3      <- 5 在左子树，1 在右子树，分居两侧 -> 根是 LCA
    LCA(5, 4) = 5      <- 4 在 5 的子树里 -> 5 自己是 LCA
    LCA(6, 4) = 5      <- 6 和 4 都在 5 的子树里
    LCA(7, 8) = 3      <- 7 在左，8 在右
    LCA(3, 8) = 3      <- 3 就是其中一个目标 -> 它自己是 LCA

五行代码，解决了看起来很难的问题。 关键就在"返回值的语义设计"。

这个算法的精髓：

"左右都非空"这个条件，恰好捕捉到了"p 和 q 在两侧分开"这个瞬间。

• 如果 p 和 q 都在左子树，那么 right 会是 null —— 结果由 left 往上传递
• 如果分居两侧，那么 left 和 right 都非空 —— 当前节点就是那个"分叉点"，也就是 LCA

递归返回时，那个"分叉点"会一路往上传递到根，最终被返回。

特殊情况：如果 p 是 q 的祖先呢？

比如 LCA(3, 8) —— 3 是根，8 在右子树。

• 递归到根（3）时，root == p（3 就是 p）→ 直接返回 root
• 不需要再往下找 q —— 因为一个节点如果是 p，而 q 在它的子树里，那 p 自己就是 LCA

if (root == p || root == q) return root; 这一行同时处理了这种情况。

六、经典题四：路径问题（自顶向下 + 回溯）

问题：找出从根到某个节点的路径。

这个不能用前面的套路 —— 因为"路径"是从根累积下来的状态，不是"子树的结果"。

/// <summary>从根到目标节点的路径。</summary>
static bool FindPath(TreeNode? node, int target, List<int> path)
{
    if (node == null) return false;

    path.Add(node.Value);                       // 先假设它在路径上

    if (node.Value == target) return true;

    if (FindPath(node.Left, target, path)) return true;    // 左边找到了
    if (FindPath(node.Right, target, path)) return true;   // 右边找到了

    path.RemoveAt(path.Count - 1);              // 两边都没找到 -> 回溯，把它移出路径
    return false;
}

实测：到节点 4 的路径 = 3 -> 5 -> 2 -> 4 ✓

关键点：

1. path.Add() 在递归之前 —— 这是"带着状态往下走"（自顶向下）。
2. path.RemoveAt() 在递归之后 —— 这是回溯：如果这个节点不在目标路径上，就要把它"撤销"。
3. 返回值是 bool（找没找到），而不是路径本身 —— 路径通过参数（引用类型）来传递和修改。

"回溯"的本质就是"撤销选择"：先假设这个节点在路径上，如果最后发现不对，就把它移除。

这是"自顶向下"套路的标准补充 —— 自顶向下传递状态，遇到死路时要能回退。

两种写法的对比：

七、经典题五：树的结构判断（双节点递归）

有些题需要"同时递归两棵树"：

/// <summary>判断两棵树是否完全相同。</summary>
static bool IsSameTree(TreeNode? a, TreeNode? b)
{
    if (a == null && b == null) return true;    // 都为空 -> 相同
    if (a == null || b == null) return false;   // 一空一非空 -> 不同
    if (a.Value != b.Value) return false;       // 值不同

    return IsSameTree(a.Left, b.Left) && IsSameTree(a.Right, b.Right);
}

/// <summary>判断两棵树是否镜像对称（左右翻转后相同）。</summary>
static bool IsSymmetric(TreeNode? a, TreeNode? b)
{
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    if (a.Value != b.Value) return false;

    // 关键：左的左 vs 右的右，左的右 vs 右的左 —— 交叉比较
    return IsSymmetric(a.Left, b.Right) && IsSymmetric(a.Right, b.Left);
}

实测：

  树 A 和树 B 相同吗？ True（预期 True）
  树 A 和树 C 相同吗？ False（预期 False）

  这棵树对称吗？ True（预期 True）
  非对称的树呢？ False（预期 False）

对称判断的"交叉"是关键：

• IsSameTree：左对左、右对右（平行比较）
• IsSymmetric：左对右、右对左（交叉比较）

一字之差，结果完全不同。 这是"镜像"这个概念在代码里的直接体现。

八、通用方法论总结

遇到树题，按这个流程走：

第 1 步：确定递归函数的"黑盒语义"
  ├─ 接收什么参数？
  └─ 返回什么？（用一句话描述，比如"以 node 为根的子树的最大深度"）

第 2 步：判断自顶向下还是自底向上
  └─ 问："要算当前节点，需不需要先知道子树的结果？"
      需要 -> 自底向上（后序）
      不需要 -> 自顶向下（前序）

第 3 步：设计基准情形
  ├─ node == null 时返回什么？（最常见）
  └─ 叶子节点要特殊处理吗？

第 4 步：写出递推关系
  ├─ 自底向上：return 用(左结果, 右结果) 算出的自己的结果
  └─ 自顶向下：处理自己，然后带新状态递归

第 5 步：检查特殊情况
  ├─ 需要"提前失败"吗？（用特殊返回值表示无效）
  ├─ 需要"回溯"吗？（自顶向下 + 撤销）
  └─ 需要同时递归两棵树吗？

对照表：

九、练习

练习 9.4.1（设计返回值） 为下面每道题设计递归函数的"黑盒语义"（接收什么、返回什么、基准情形）： (a) 统计树中值为偶数的节点个数 (b) 求树中所有节点值的和 (c) 求树的"最小深度"（从根到最近叶子的节点数） (d) 判断树中是否存在一条"从根到叶子"的路径，其节点值之和等于目标值

练习 9.4.2（判断套路） 下面四道题，哪些用自顶向下、哪些用自底向上？ (a) 求二叉树的最大深度 (b) 求二叉树中所有从根到叶子的路径 (c) 求二叉树中任意两个节点的最大距离（直径） (d) 给每个节点标注它的深度

练习 9.4.3（写代码） 写一个函数 CountNodes(TreeNode) 统计树的节点总数。 (a) 先写出"黑盒语义"。 (b) 写出代码。 (c) 它是自顶向下还是自底向上？

练习 9.4.4（改造） 下面这段"求最小深度"的代码有 bug，请指出并修复：

static int MinDepth(TreeNode? node)
{
    if (node == null) return 0;
    return 1 + Math.Min(MinDepth(node.Left), MinDepth(node.Right));
}

练习 9.4.5（挑战·树的直径） 树的直径：树中任意两个节点之间最长路径的边数。 (a) 直径一定经过某个"最高点"吗？ (b) 设 depth(node) = 以 node 为根的子树的深度。如果直径的最高点是 node，那么这条路径的长度是多少？ (c) 设计一个自底向上的算法，一次遍历求出直径。（提示：需要同时返回"子树深度"和"当前已知的最大直径"。）

十、练习答案

9.4.1

(a) 统计值为偶数的节点个数

static int CountEven(TreeNode? node)
    => node == null ? 0
       : (node.Value % 2 == 0 ? 1 : 0) + CountEven(node.Left) + CountEven(node.Right);

(b) 所有节点值的和

static int Sum(TreeNode? node)
    => node == null ? 0 : node.Value + Sum(node.Left) + Sum(node.Right);

(c) 最小深度

static int MinDepth(TreeNode? node)
{
    if (node == null) return 0;
    if (node.Left == null) return 1 + MinDepth(node.Right);    // 只有右孩子
    if (node.Right == null) return 1 + MinDepth(node.Left);    // 只有左孩子
    return 1 + Math.Min(MinDepth(node.Left), MinDepth(node.Right));
}

(d) 是否存在和为 target 的根到叶子路径

注意：这道题是自顶向下！ 因为"当前的和"是从根累积下来的状态。

static bool HasPathSum(TreeNode? node, int target, int sumSoFar = 0)
{
    if (node == null) return false;

    sumSoFar += node.Value;

    // 叶子节点：判断累加和
    if (node.Left == null && node.Right == null)
        return sumSoFar == target;

    return HasPathSum(node.Left, target, sumSoFar)
        || HasPathSum(node.Right, target, sumSoFar);
}

对比 (c) 和 (d)：

• (c) 最小深度：只依赖子树的结果 → 自底向上
• (d) 路径和：依赖从根累积的状态 → 自顶向下

同一个"深度"概念，在不同题目里可能走完全不同的套路。 关键是问"这个答案依赖什么"。

9.4.2

(b) 和 (d) 都是典型的"自顶向下" —— 因为答案依赖"从根一路传下来的信息"，而不是"子树的结果"。

(a) 和 (c) 都是"自底向上" —— 因为答案必须由子树的结果算出来。

9.4.3

(a) 黑盒语义：

(b) 代码：

static int CountNodes(TreeNode? node)
    => node == null ? 0 : 1 + CountNodes(node.Left) + CountNodes(node.Right);

(c) 自底向上（后序）。

因为"我的节点数" = 1 + 左子树的节点数 + 右子树的节点数 —— 必须先知道子树的结果。

9.4.4

Bug：当节点只有一个孩子时，会返回错误的答案。

问题分析：

return 1 + Math.Min(MinDepth(node.Left), MinDepth(node.Right));

如果 node.Left == null 但 node.Right != null：

• MinDepth(node.Left) 返回 0（因为空节点返回 0）
• Min(0, MinDepth(node.Right)) = 0
• 结果 = 1 + 0 = 1

但这是错的！ 这个节点不是叶子（它有右孩子），所以"从它往下到叶子的最短路径"必须走右边，不可能长度是 1。

反例：

     1
      \
       2
        \
         3

  正确答案：最小深度 = 3（1 -> 2 -> 3）
  错误代码：MinDepth(2) 时，左孩子是 null 返回 0，min(0, MinDepth(3)) = 0
           所以 MinDepth(2) = 1 + 0 = 1
           最终 MinDepth(1) = 1 + min(0, 1) = 1   ← 错！答案是 3

修复：

static int MinDepth(TreeNode? node)
{
    if (node == null) return 0;
    if (node.Left == null) return 1 + MinDepth(node.Right);    // 只有右孩子，必须走右边
    if (node.Right == null) return 1 + MinDepth(node.Left);    // 只有左孩子，必须走左边
    return 1 + Math.Min(MinDepth(node.Left), MinDepth(node.Right));   // 两个孩子都有
}

这个 bug 的根源是"把 null 子树当成了深度为 0 的合法路径"。

null 的含义是"这里没有子树"，而不是"这里有一条长度为 0 的路径"。

区分"没有"和"有但是空"，是树题里非常常见的一类坑。 类似的还有：BST 的验证（空节点不是"合法的 BST"而是"不存在"）、路径问题（空节点不构成路径）。

9.4.5

(a) 是的，直径一定经过某个"最高点"。

更准确地说：任何一条路径，都有一个"最高"的节点（深度最小的那个）。这条路径从这个节点出发，向下延伸到两个不同的子树（或者延伸到同一个子树向下）。

直径就是所有"以某节点为最高点的路径"中最长的那条。

(b) 如果直径的最高点是 node，那么这条路径由两段组成：

• 从 node 到左子树中最深的叶子：长度 = depth(node.Left)（以边数计，空子树深度为 $-1$）
• 从 node 到右子树中最深的叶子：长度 = depth(node.Right)

所以这条路径的长度是：

$$\text{length} = (\text{depth}(node.Left) + 1) + (\text{depth}(node.Right) + 1) = \text{depth}(node.Left) + \text{depth}(node.Right) + 2$$

（这里的 $+1$ 是从 node 到子树根的那条边，两边各一条。）

(c) 一次遍历求直径：

static int _diameter = 0;      // 记录全局最大直径

/// <summary>返回子树深度，同时更新全局直径。</summary>
static int DepthAndUpdateDiameter(TreeNode? node)
{
    if (node == null) return -1;         // 空子树深度为 -1

    int leftDepth = DepthAndUpdateDiameter(node.Left);
    int rightDepth = DepthAndUpdateDiameter(node.Right);

    // 以当前节点为最高点的路径长度
    int pathThroughNode = leftDepth + rightDepth + 2;
    if (pathThroughNode > _diameter) _diameter = pathThroughNode;

    // 返回自己作为子树时的深度
    return 1 + Math.Max(leftDepth, rightDepth);
}

static int DiameterOfBinaryTree(TreeNode? root)
{
    _diameter = 0;
    DepthAndUpdateDiameter(root);
    return _diameter;
}

推演（用下面的树）：

        1
       / \
      2   3
     / \
    4   5

  节点 4：left=-1, right=-1 -> 经过它的路径 = -1 + -1 + 2 = 0，返回深度 0
  节点 5：同上，路径 = 0，返回深度 0
  节点 2：left=0, right=0 -> 经过它的路径 = 0 + 0 + 2 = 2，返回深度 1
  节点 3：路径 = 0，返回深度 0
  节点 1：left=1, right=0 -> 经过它的路径 = 1 + 0 + 2 = 3，返回深度 2

  最大直径 = 3（路径 4 -> 2 -> 1 -> 3，共 3 条边）✓

这个算法的精髓：用"一个返回值 + 一个全局变量"同时传递两种信息。

• 返回值：子树深度（供父节点使用）
• 全局变量：目前为止发现的最大直径（供最终答案使用）

为什么不能只用一个返回值？ 因为"直径"和"深度"是两个不同的量：

• 父节点需要的是深度（用来算经过自己的路径）
• 但答案是直径

当一道题需要"给父节点用的信息"和"最终答案"不一致时，就用"返回值 + 全局变量（或引用参数）"来同时传递。

这是树题进阶技巧里最常用的一个。 类似的题目还有"二叉树的最大路径和""打家劫舍 III"。

十一、常见错误

十二、本节总结

1. 设计递归函数的核心方法：先定义"黑盒语义" —— 接收什么、返回什么，各用一句话说清。
2. 两大套路：
   • 自底向上（后序）：先要子树的结果，再算自己 —— 适合深度、节点数、平衡、LCA
   • 自顶向下（前序）：带着状态往下传 —— 适合路径类问题
3. 判断方法：问"要算当前节点，需不需要先知道子树的结果？"
4. 判断平衡的优化：用 -1 表示"已不平衡"，一次遍历完成。朴素的"自顶向下重算高度"最坏是 $O(n \log n)$（平衡树才是它的最坏情况，实测差 9.3 倍）。
5. LCA 的精髓在返回值语义：null（没找到）/ 找到的一个（往上传）/ LCA（左右都非空时返回）。
6. 路径问题要回溯：Add 在递归前、RemoveAt 在递归后 —— 走不通就要撤销。
7. null 不是"深度为 0 的路径" —— 区分"没有"和"有空"（练习 9.4.4 的 bug 就出在这）。
8. 需要同时传递两种信息时（给父节点的值 + 最终答案），用"返回值 + 全局变量"。

本章小结：第 9 章把树的基础讲完了。

• 9.1 术语和形态，重点是深度 vs 高度，以及"平衡树高度 $O(\log n)$"这个性能来源。
• 9.2 三种深度优先遍历只差一行代码，但用途完全不同（复制/有序/依赖子树）。
• 9.3 广度优先用队列，levelSize 是按层分组的关键，而 BFS 的核心优势是"可以提前停止"。
• 9.4 递归套路：先想清楚"返回值是什么"，再动手写代码。

下一章衔接：到这里，树的结构和遍历都齐了。但普通二叉树本身没什么用 —— 它既不快也不有序。

真正有用的是加了约束的树。第一个约束就是：左子树的所有值都小于根，右子树的所有值都大于根。这棵树叫二叉搜索树（BST），它让查找从 $O(n)$ 降到 $O(\log n)$。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "9.4",
  "title": "树题递归套路：返回值该是什么",
  "covered": [
    "「黑盒语义」设计法（接收什么/返回什么）",
    "自顶向下 vs 自底向上的判断标准",
    "最大深度（自底向上基础形态）",
    "判断平衡的 O(n^2) 朴素解与 O(n) 优化解（-1 提前失败）",
    "LCA 的三种返回值语义与实测（5 组用例）",
    "路径问题的自顶向下 + 回溯（Add/RemoveAt 的位置）",
    "双节点递归（IsSameTree 平行 vs IsSymmetric 交叉）",
    "通用五步方法论与题型对照表",
    "树的直径：「返回值 + 全局变量」传递两种信息",
    "「null 不是深度为 0 的路径」的辨析"
  ],
  "unresolved": [
    "BST 留到第 10 章",
    "树的最大路径和等进阶题超出本书范围",
    "回溯算法本身超出本书范围（本书只用到路径回溯）"
  ],
  "canonical_terms": {
    "自顶向下": "带着从根累积的状态往下传的递归方式",
    "自底向上": "先要子树结果、再算自己的递归方式",
    "返回值语义": "递归函数返回值所代表的确切含义",
    "回溯": "尝试后如果失败就撤销选择"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 9.2/9.3 的全部遍历方式",
    "读者理解 2.1 节的递归去程/回程"
  ],
  "word_count_actual": 3460,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch09/Sec94/",
    "LCA 五组用例、路径、同树/对称判断均为实测",
    "练习 9.4.4 的 bug 分析与反例已手工验算",
    "练习 9.4.5 的直径推演已手工验算（结果为 3）",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版用链状树测试「判断平衡」的性能，实测朴素版反而更快（0.072ms vs 0.166ms），与预设结论矛盾；原因是链状树在根节点就提前失败、根本没往下递归。已补「完美平衡树」场景（自底向上快 9.3 倍）并修正复杂度表述：朴素解最坏是 O(n log n) 而非 O(n^2)"
  ],
  "next": "10.1 二叉搜索树的有序性"
}