TikTok 正整数树向上路径和：祖先前缀与退出回滚

题意与假设

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

• 全节点正整数，target>0，路径非空、单向上行；不要求从根开始，也不要求叶子结束。

解题路线

1. 上行连续路径与同一祖先链上的下行路径集合相同。DFS 到节点的 root前缀和 S，若祖先之前某前缀为 S-target，则中间链之和为 target。
2. 当前分支保存前缀集合，初始0允许根起点。检查后加入当前 S，离开分支时删除，避免兄弟支路相互拼成不存在路径。
3. 正数使一条分支前缀严格递增，集合删除无需频次；若扩展零/负数，重复前缀要计数，不能直接 set.remove。
4. 迭代栈用进入/退出事件实现回滚，避免深递归。另一解对每节点向上累加并在超过target停止，最坏仍 O(nh)。

手动走一遍

根3、左2、左下4，target6 可由4→2；target9 可4→2→3。根左右分别2/4，target6不能把左2与右4拼接，因为路径需要穿根且改变方向。

Python 参考实现

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

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

def has_ancestor_path_sum(root, target):
    """Positive integer nodes, positive target; path follows parents only.
    DFS exit markers maintain sums for each root-to-current branch."""
    if target <= 0:
        return False
    prefix = {0}
    stack = [(root, 0, False)]
    while stack:
        node, total, exiting = stack.pop()
        if node is None:
            continue
        if exiting:
            prefix.remove(total)
            continue
        if node.value <= 0:
            raise ValueError('positive values required')
        total += node.value
        if total - target in prefix:
            return True
        prefix.add(total)
        stack.append((node, total, True))
        stack.append((node.right, total, False))
        stack.append((node.left, total, False))
    return False

复杂度

哈希集合平均 O(n) 时间、O(h) 当前分支状态；迭代工作栈 O(h)，退化 O(n)。整数前缀位数成本另计。

易错点与追问

容易失分的边界

• 写成任意两节点路径。
• 前缀不回滚，跨兄弟误匹配。
• 允许零负数却仍用集合计数。

继续深挖

• 若允许零/负数如何改？
• 要输出路径节点如何保存对应前缀位置？