题目重点：两片不同叶子之间的路径若全升或全降才合法；用每节点到叶的升降 DP 拼接，并解释‘最长单调子路径’与‘叶到叶’的区别。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 树节点是整数，单调指相邻值严格递增或严格递减，相等值中断。长度按节点数计；两端必须是不同的叶节点。
- 若树少于两片叶，或没有一条完整叶到叶路径严格单调，返回 0。题目的 7→9 是局部单调片段但 7 不是叶，因此不单独计为叶到叶答案。
- 树是无环、无共享节点的二叉树；递归代码适合深度不超过运行环境递归限制的输入。
解题路线
- 后序 DFS 对每个节点维护 inc 和 dec：从当前节点沿子树向下，到某片叶为止的最长严格递增/递减路径长度；若没有这种完整路径，对应状态记 0。叶节点的两个状态都为 1。
- 父节点值小于子节点值时，可把子节点的 inc 延长一格作为父节点 inc；父节点值大于子节点值时同理延长 dec。一个孩子可能只能提供其中一个方向的完整叶路径。
- 完整叶到叶路径的最近公共祖先必须有左右两侧叶。若从左叶升到节点再降到右叶，按节点向下看是左侧 dec 加右侧 inc；另一方向用左侧 inc 加右侧 dec。两个长度相加后减去公共祖先的重复计数 1。
- 对每个节点更新全局最优。任何叶到叶路径有唯一最近公共祖先，且若它单调，上述两种方向之一一定对应两侧 DP 状态，因此所有合法路径都会被考虑。
手动走一遍
题目树 root=10，左叶 12，右子树 7 的叶为 3 和 9。节点 10 向左是上升 10→12 长 2，向右是下降 10→7→3 长 3，拼接得 2+3−1=4，即 12→10→7→3。路径 12→10→7→9 在 7→9 处反向，不合法。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Longest strictly monotonic path whose two endpoints are distinct leaves."""
from dataclasses import dataclass
@dataclass
class Node:
value: int
left: "Node | None" = None
right: "Node | None" = None
def longest_leaf_to_leaf_monotonic(root: Node | None) -> int:
best = 0
def visit(node: Node | None) -> tuple[int, int]:
nonlocal best
if node is None:
return 0, 0
if node.left is None and node.right is None:
return 1, 1
child_info = []
inc, dec = 0, 0
for child in (node.left, node.right):
if child is None:
child_info.append((0, 0))
continue
child_inc, child_dec = visit(child)
rising = 1 + child_inc if node.value < child.value and child_inc else 0
falling = 1 + child_dec if node.value > child.value and child_dec else 0
inc = max(inc, rising)
dec = max(dec, falling)
child_info.append((rising, falling))
left, right = child_info
if left[0] and right[1]:
best = max(best, left[0] + right[1] - 1)
if left[1] and right[0]:
best = max(best, left[1] + right[0] - 1)
return inc, dec
visit(root)
return best
复杂度
每个节点仅后序访问一次，O(n) 时间；递归栈 O(h)，h 为树高，链形最坏 O(n)。每节点只向父级返回两个整数，不需保存全部叶路径。
易错点与追问
容易失分的边界
- 把任意两个内部节点间的最长单调子路径当答案，会接受不以叶结尾的局部 7→9 或其他片段。
- 在最近公共祖先处把两条同向的向下递增路径直接拼起来；从左叶走向父节点时方向实际上反过来。
- 等值边当作非严格单调，或把一侧没有到叶的状态 0 误拼成有效路径。
- 把题目看成某一条根到叶路径，忽略跨左右子树的叶到叶路径。
继续深挖
- 若面试官其实允许任意端点的最长单调路径，状态和基线怎样改变？根到单叶的链也将有答案。
- 如果节点值可重复且‘非递减/非递增’也算单调，应怎样改严格比较与并列路径定义？
- 若树极深或由流输入，如何改为显式后序栈并控制内存？
