那么 边界 条件 是什 么呢 ，就 是节 点为 空的 时候 ，直 接返 回0 即可 。
有了 递推 公式 和边 界条 件， 我们 来看 下最 终代 码
1 public int rob(TreeNode root) {
2 int[] robHelp = robHelper(root);
3 //取偷根节点和不偷根节点的最大值
4 return Math.max(robHelp[1], robHelp[0]);
5 }
6
7 public int[] robHelper(TreeNode root) {
8 //边界条件
9 if (root == null)
10 return new int[2];
11 //这里的left是个长度为2的一维数组，其中left[0]表示不偷root.left节点
12 //所能偷窃的最大金额，left[1]表示偷root.left节点所能偷窃的最大金额。
13 int[] left = robHelper(root.left);
14 //right节点同left
15 int[] right = robHelper(root.right);
16 //Math.max(right[0], right[1]), root.val + left[0] + right[0]表示
17 //的是不能偷当前节点，所以可以偷两个子节点，也可以不偷子节点，我们取最大的。
18 //root.val + left[1] + right[1]表示的是偷当前节点，所以不能偷两个子节点。
19 return new int[]{Math.max(left[0], left[1]) +
20 Math.max(right[0], right[1]), root.val + left[0] + right[0]};
21 }
总结
如 果 对 二 叉 树 的 遍 历 方 式 比 较 熟 悉 的 话 ， 上 面 代 码 一 看 就 知 道 ， 他 和 二 叉 树 的 后 续 遍 历
非 常 相 似 ， 是 完 全 从 下 到 上 的 一 种 遍 历 方 式 ， 每 一 个 节 点 都 记 录 了 两 种 状 态 ， 一 种 是
偷 ， 一 种 是 不 偷 。 每 次 从 下 往 上 走 的 时 候 这 两 种 状 态 都 会 记 录 下 来 …… 一 直 到 根 节 点 ，
最后 我们 只需 要返 回偷 根节 点和 不偷 根节 点的 最大 值即 可。
●465. 递归和动 态规 划解 三角 形最小路径和
●470，DFS和B FS 解合 并二 叉树
●455，DFS和B FS 解被 围绕 的区域
●445，BFS和D FS 两种 方式 解岛屿数量
我的内容管理
展开
