打家劫舍 III

有人想：偶数层全偷、奇数层全不偷，二选一取大。但局部结构千变万化，这种「整层一刀切」常常不是最优，必须逐户决策。

难点在于：父亲偷不偷，取决于孩子偷没偷。所以每个节点不返回一个数，而是返回一对：左边是「不偷我」的最大值，右边是「偷我」的最大值。

后序遍历：先把最底层算清楚：树形 DP 一律后序：先递归到底，把孩子的账算出来，父亲才有依据。我们从最底下两个叶子开始：值为 3 的那户，和值为 1 的那户。

叶子户结账：偷=自己的钱，不偷=0：叶子没有孩子。偷它，就赚它自己的钱；不偷它，赚 0。所以左边那户 3 回传 (0, 3)，右边那户 1 回传 (0, 1)。这就是递归的底。

灵魂帧 · 偷父亲：只能配「孩子不偷」：看值为 2 的这户。它左孩子是空、右孩子是那户 3。如果偷它，相邻的孩子就一律不能偷，只能取孩子那对里「不偷」的数：2 加 0 加 0，偷它只赚 2。

灵魂帧 · 不偷父亲：孩子各自挑大的：如果不偷这户 2，孩子就解放了：每个孩子在自己那对里随便挑大的。左边空取 0，右边那户 3 偷它更划算取 3。不偷它反而能赚 3。所以这户 2 回传 (不偷3, 偷2)。

右边那户 3 同样结一次账：对右子树重复同一套：值为 3 的这户，偷它配孩子不偷得 3；不偷它让孩子 1 自己挑大的得 1。它回传 (不偷1, 偷3)。注意偷它 3 比不偷它 1 更优。

灵魂帧 · 根节点合并左右两对账：回到根 3。它两个孩子的账已经备好：左孩子 (不偷3, 偷2)、右孩子 (不偷1, 偷3)。偷根时孩子都不能动，取它们的「不偷」：3 加 3 加 1 等于 7。

灵魂帧 · 根的另一笔账与最终答案：不偷根时，两个孩子各挑大的：左取 max(3,2)=3、右取 max(1,3)=3，合计 6。根回传 (不偷6, 偷7)。最后在根这对里取大的：max(6,7) 等于 7，正是答案。

一句话本质：偷我，就只能要孩子的「不偷」；不偷我，孩子各自挑大的。把这对账往上传，根那一对里取大的就是答案。

雷区实演 · 为什么不偷必须取 max：换条链 4 到 1 到 2 到 3。不偷根 4 时，孩子 1 那条线如果机械地偷孩子，反而错过更值钱的孙子。必须让孩子在「偷 / 不偷」里取大，才能把深处的钱捞上来。

面试追问：面试时这三问几乎必问：返回一对的理由、与记忆化递归的等价、和数组版的迁移关系。能讲清就说明真懂了。

迁移阶梯：学会「每个节点回传一对状态」后，二叉树最大路径和、监控二叉树都是同一套：先想清每个节点要向上汇报哪几种状态，再写后序合并。点开树专题，让小欧带你把这套迁移练熟。

边界三连：边界先看三种：空树回 0、单节点直接偷、以及本例完整跑出 7。空节点的 (0,0) 是整个递归能收住的关键。