题目重点：利用 min-parent 性质剪掉不可能改进答案的子树，说明最坏仍需线性扫描。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版每个内部节点有两个 child 且 value=min(left.value,right.value)，叶子保存任意整数；返回严格大于全局最小的最小值，无则 None。
- 题目没有明确空树返回、是否所有内部节点都有双子、相同最小值的分布；这些均为训练接口契约。
解题路线
- 根的值为全局最小。遍历时如果节点值等于根最小值，需要继续探索孩子，因为第二小值可能藏在任一条重复最小值分支。
- 若节点值>根最小值，则它是该子树最小值：整个子树的其他值都≥它，所以用它更新当前答案后可直接剪枝，无须进入后代。
- 剪枝正确性来自 min-parent 不变量，而不是树是否平衡。最坏情况下许多内部节点都等于根值，仍会访问 O(N) 节点；仅在额外保证唯一最小链及树高度 O(log N) 等条件下才可能近似对数。
- 输入若不保证 min-parent，剪枝不正确；可以先验证全树不变量，但验证本身 O(N)。
手动走一遍
根 2，左子树根 2、叶子 2/5，右子树根 3、叶子 3/9：根下左侧继续找 5，右侧节点 3 更新答案并剪去 3/9，最终第二小为 3。若整树全是 2，返回 None。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from dataclasses import dataclass
@dataclass
class Node:
value: int
left: "Node | None" = None
right: "Node | None" = None
def second_distinct_min(root: Node | None) -> int | None:
if root is None:
return None
minimum = root.value
best = None
stack = [root]
while stack:
node = stack.pop()
if node.value > minimum:
best = node.value if best is None else min(best, node.value)
# A min-parent tree guarantees every descendant >= this node.
continue
if node.left is not None:
stack.append(node.left)
if node.right is not None:
stack.append(node.right)
return best
复杂度
访问节点数最坏 O(N)，迭代栈最坏 O(H) 到 O(N) 取决于待遍历前沿；平衡树通常 O(H) 深度的递归替代写法，但多个同值分支仍可能让时间线性。训练代码经 10,000 棵随机 min-parent 树与全节点集合排序对照。
易错点与追问
容易失分的边界
- 把第二小节点误当根的另一个 child。
- 遇到一个大于根的节点后还继续遍历它的后代。
- 重复最小值只沿一条分支探索。
- 无额外条件就宣称 O(log N)。
- 返回第二个节点而非第二个不同数值。
继续深挖
- 如果节点只保证父≤子而非等于两孩子最小，剪枝还成立吗？
- 树巨大且节点远程分页时怎样减少 IO？
- 需要第 K 小不同值时如何改？
- 如何在更新树后维护第二小缓存？
