二叉树最长同值路径：两条向下臂在节点拼接

题目重点：路径长度按边数，同值重复树不是严格BST。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

一般二叉树，值可重复；源文字称BST但与重复同值路径存在歧义，本文明确采用二叉树训练合同。
路径无重复节点，可从任意节点到任意节点，空树返回0；共享节点/循环输入拒绝。

解题路线

down[u]是从u向下能走的最长同值边数。左右孩子值同u时对应臂为1+down[child]，不同则0。
以u为最高公共祖先的同值路径长度是leftArm+rightArm，更新全局答案；返回给父节点的只能max两臂，不能把叉形继续向上。
先显式遍历建order，再反序处理，避免长链递归栈。按id而非value保存状态，重复值节点仍是不同对象。

手动走一遍

根5，左5下有5，右5：左右臂2和1，最长跨根3边。只有一个节点长度0；三节点值1→2→1不能跨不同值节点连接。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from dataclasses import dataclass


@dataclass(eq=False)
class Node:
    value:int
    left:object=None
    right:object=None


def longest_same(root):
    if root is None:return 0
    order=[root];seen={id(root)}
    for node in order:
        for child in (node.left,node.right):
            if child is not None:
                if id(child) in seen:raise ValueError("not a tree")
                seen.add(id(child));order.append(child)
    down={};answer=0
    for node in reversed(order):
        l=1+down[id(node.left)] if node.left is not None and node.left.value==node.value else 0
        r=1+down[id(node.right)] if node.right is not None and node.right.value==node.value else 0
        answer=max(answer,l+r);down[id(node)]=max(l,r)
    return answer

复杂度

O(n)时间、O(n)空间；递归版辅助栈O(h)，但示例order/down确实O(n)。

易错点与追问

容易失分的边界

把节点数当边数导致全结果+1。
严格BST一般不允许相同键，若坚持严格BST合同这题常退化，需澄清。

继续深挖

返回实际路径怎样保存每臂后继并重建？
边有权时，负权臂是否应保留0的空延伸？