题目重点：找任意节点开始的向下严格递增路径，用后序长度和后继指针避免反复复制路径。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练父→子方向、child.value>parent.value，不要求差值1；返回整条Node路径，多个最优任意一个。不是允许左→父→右折返的无向单调路径。
- 追加任意方向严格递增简单路径训练，用longest_increasing_undirected_path；可低值子→父→高值子，不要求从root。排序是否允许相等与方向必须明确，原函数仍只向下。
解题路线
- 后序求down[node]，初值1；仅对更大值child考虑1+down[child]，选择最大并记following[node]。child不更大时递增链在边界断开，但其内部仍可独立成为全局最好起点。
- 全局比较每个节点down，记录bestStart，不只从root开始。某子树根前面有下降仍可以形成最长路径，根起点限定会漏解。
- 使用显式(节点,ready)stack保证children先完成，再计算parent。记录length和一个successor，而非每节点复制整条path；最后从bestStart跟following一次重构。
- 正确性来自向下路径第一条边只能选一个child；满足递增的后继最优由子问题给出，取max即节点最优。路径不能同时连接两个child，因为那会改变方向合同。
- 值重复不满足严格递增，+2或+100都允许。要求child=parent+1是另一变体，只需改边合法条件但题意不能混称。
- 任意方向变体后序分别维护inc（当前向下逐增）与dec（当前向下逐减），在node连接反向dec臂+node+inc臂，长度inc+dec−1。两臂首child分别<和>当前，不会是同child。记录两类next，最后低臂reverse再拼高臂。
手动走一遍
根5→左2→右9→子10最长可为2,9,10，虽然不是从root开始且跳2→9不连续。5的另一个child5不能接入严格递增链。返回Node对象能保留重复值节点身份。 BST根3、左2→左1、右5，3→2→1是下降，所以向下递增最长3,5（长度2）；任意方向可1,2,3,5长度4。不能把两种函数的答案混用。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class Node:
def __init__(self,value,left=None,right=None):self.value=value;self.left=left;self.right=right
def longest_increasing_path(root):
"""Strict child>parent downward path, return Node objects; any tie accepted."""
if root is None:return []
# Postorder lengths and next pointers, reconstruct once rather than copying paths.
down={};following={};stack=[(root,False)];best_start=root;best_length=0
while stack:
node,ready=stack.pop()
if not ready:
stack.append((node,True))
for child in (node.right,node.left):
if child is not None:stack.append((child,False))
continue
length=1;successor=None
for child in (node.left,node.right):
if child is not None and child.value>node.value and down[child]+1>length:
length=down[child]+1;successor=child
down[node]=length;following[node]=successor
if length>best_length:best_length=length;best_start=node
path=[]
while best_start is not None:
path.append(best_start);best_start=following[best_start]
return path
def longest_increasing_undirected_path(root):
"""Strictly increasing along any simple tree path, either traversal direction.
Does not require BST ordering; equal-value edges cannot be part of a path.
"""
if root is None:return []
increasing={};decreasing={};next_up={};next_down={}
stack=[(root,False)];best=root;best_length=0
while stack:
node,ready=stack.pop()
if not ready:
stack.append((node,True))
for child in (node.left,node.right):
if child is not None:stack.append((child,False))
continue
inc=dec=1;up=down=None
for child in (node.left,node.right):
if child is None:continue
if child.value>node.value and increasing[child]+1>inc:inc=increasing[child]+1;up=child
if child.value<node.value and decreasing[child]+1>dec:dec=decreasing[child]+1;down=child
increasing[node]=inc;decreasing[node]=dec;next_up[node]=up;next_down[node]=down
if inc+dec-1>best_length:best_length=inc+dec-1;best=node
lower=[];current=next_down[best]
while current is not None:lower.append(current);current=next_down[current]
result=list(reversed(lower));current=best
while current is not None:result.append(current);current=next_up[current]
return result
复杂度
O(N)计算+O(L)重构，当前down/following O(N)空间、stack O(h)常规树后序；输出O(L)。若每层复制子path，退化树会达O(N²)时间，不能只因遍历一次就说线性。 任意方向版本O(N)计算/O(L)重构，O(N)双臂/next表；树路径唯一，所有严格递增路径在其最高祖先处分为一低臂一高臂，覆盖所有候选。
易错点与追问
容易失分的边界
- 将递增条件写成child=parent+1会漏允许跳值的路径。
- 只比较根的链长会漏子树独立最长路径。
继续深挖
- 如果允许任意方向单调路径，可通过父节点连接两侧吗？需要分别维护递增/递减臂与合并条件，不能直接用当前单child递推。
- Tie要求最早遍历或字典序最小，需要怎样调整记录规则与比较成本？
