TikTok 二叉树最大路径和：单臂 Gain、双臂候选与路径重建

题目重点：路径可不经过根或叶，正确处理全负数，保存后继指针而非逐节点复制路径。

题意与假设

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

训练节点为整数值，路径是非空、不重复节点的相邻序列；可经过某节点向两边延伸，但不分叉。
空树明确返回(0,[])作为API约定，非空全负树必须返回一个最大值节点而不是空路径0。
同和答案返回按左后序先遇到的候选；单臂收益同正值时优先左边，不声称最短或字典序最小。
输入须是真正二叉树，不允许循环或同节点被多个父引用；示例返回节点对象路径，显示时可取value。

解题路线

定义gain(node)为从node开始、只向下一条分支延伸的最大和。它将作为父节点路径的一条臂，因此最多选左或右之一：node.value+max(0,gain(left),gain(right))。
以node为最高拐点的完整候选可同时使用左右两臂：node.value+max(0,gain(left))+max(0,gain(right))。这个候选只更新全局best，不作为gain返回给父节点，否则会产生三叉路径。
每条简单路径有唯一距根最近的节点，两端分别位于它的不同子树或节点本身。遍历所有拐点并选每侧最优非负臂，能覆盖所有可能路径，也不要求路径通过全树root。
best初始化为尚未有候选而非0；负臂不延伸，但拐点本身始终存在。全负树中最大单节点会被保留，避免把允许丢掉负臂误解成允许非空树取空路径。
保存每个node选中的单臂后继successor，再记录最佳拐点及当时正收益左右起点。最终沿左臂向下收集后反转，接center，再接右臂向下序列，即得到连续路径。重复节点值不会混淆，因为指针按节点身份处理。
不要为每个gain返回一个完整节点list，链状树会反复复制越来越长路径而成O(n²)。本实现只保存一个后继指针，最终最佳路径构建一次；为避免深递归限制，先用显式栈生成后序。
输入结构检测用节点身份seen，重复遇到就拒绝循环或共享子节点。额外seen/postorder是此实现的O(n)成本；如果题目保证树且仅返回和，可以递归O(h)调用栈，但最坏链高h=n。
独立对照在小树上枚举所有端点，用无向邻接遍历求每一对唯一简单路径的和，再核对返回路径的节点不重复、邻接性和总和。另用深度5,000链检查显式栈可工作。

手动走一遍

树−10左9右20，20孩子15和7：全局答案在20处15→20→7，总42，不经过根。gain(20)=35，不是42；其父若拿42继续加会非法分叉。全负[-5,−2,−9]返回节点−2。

Python 参考实现

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

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

from dataclasses import dataclass


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


def maximum_path(root):
    if root is None:
        return 0, []
    stack, seen, postorder = [(root, False)], set(), []
    while stack:
        node, exiting = stack.pop()
        if exiting:
            postorder.append(node)
            continue
        if node in seen:
            raise ValueError('input must be a tree without shared children or cycles')
        if type(node.value) is not int:
            raise ValueError('node values must be integers')
        seen.add(node)
        stack.append((node, True))
        if node.right is not None:
            stack.append((node.right, False))
        if node.left is not None:
            stack.append((node.left, False))
    gain, successor = {}, {}
    best, center, arms = None, None, (None, None)
    for node in postorder:
        left_gain = max(0, gain.get(node.left, 0))
        right_gain = max(0, gain.get(node.right, 0))
        through = node.value + left_gain + right_gain
        if best is None or through > best:
            best, center = through, node
            arms = (node.left if left_gain > 0 else None,
                    node.right if right_gain > 0 else None)
        if left_gain >= right_gain and left_gain > 0:
            successor[node] = node.left
        elif right_gain > 0:
            successor[node] = node.right
        else:
            successor[node] = None
        gain[node] = node.value + max(left_gain, right_gain)

    def descend(node):
        chain = []
        while node is not None:
            chain.append(node)
            node = successor[node]
        return chain

    left, right = map(descend, arms)
    return best, list(reversed(left)) + [center] + right

复杂度

时间O(n)，后序、身份集合、gain与successor字典O(n)工作空间，最终路径O(p)，p≤n。每节点常数次处理，重建不逐节点复制。只求和的递归版工作栈O(h)，但此带检测/重建实现按实际O(n)声明。

TikTok 二叉树最大路径和：单臂 Gain、双臂候选与路径重建

题意与假设

解题路线

手动走一遍

Python 参考实现

复杂度

易错点与追问

容易失分的边界

继续深挖

复制失败，请手动复制微信号