TikTok 树形打家劫舍：选与不选的后序状态

题意与假设

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

• 题名是House Robber III；训练无环二叉树、父子不可同时取，空选择允许，值可负。
• 代码只返回最大收益，不把相同深度一律选/不选。

解题路线

1. 每节点take=自身值+左右skip，skip=max(左take,左skip)+max(右take,右skip)。父子约束切断后，两个子树可独立取最优。
2. 必须后序计算孩子状态；迭代进入/退出事件保证依赖已完成，并避免深递归。
3. 按奇偶层求和不总正确，因为不同支路可在不同深度做决定。局部选更大父子也会忽略孙子。
4. 返回root两状态最大，空树0；负值可选择不取。若需具体节点集合，要按状态回溯。

手动走一遍

根3、左2右3，左有右3、右有右1，最优3+3+1=7。全负值时空选择收益0；若必须选至少一项，需要另定义状态。

Python 参考实现

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

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

def rob_tree(root):
    """Node.value/left/right; acyclic disjoint tree. Empty selection allowed."""
    state = {}
    stack = [(root,False)]
    while stack:
        node,exit=stack.pop()
        if node is None:
            continue
        if not exit:
            stack.append((node,True));stack.append((node.right,False));stack.append((node.left,False))
        else:
            ls,lt=state.get(id(node.left),(0,0));rs,rt=state.get(id(node.right),(0,0))
            skip=max(ls,lt)+max(rs,rt)
            take=node.value+ls+rs
            state[id(node)]=(skip,take)
    return max(state.get(id(root),(0,0)))

复杂度

O(n)时间；代码状态表O(n)、工作栈O(h)，不能将此实现空间写成纯O(h)。递归不存全表可O(h)。

易错点与追问

容易失分的边界

• 按奇偶层套答案。
• 只算take漏skip。
• 状态表空间漏计。

继续深挖

• 如何回溯选中节点？
• 一般图为何不能照搬树DP？