337. 打家劫舍 III

这道题依旧是使用dp解决,我们需要维护好每个节点的两个值,一个是偷的值rob,一个是不偷的值notRob

判断一个房间偷不偷分为两点

如果偷,那么左右子节点不能偷,也就是说rob(node) = notRob(left) + notRob(right)

如果不偷,那么就要考虑偷左右偷与不偷的情况,因为二者是同级的,所以直接分开讨论,有三种情况

左偷右不偷,左不偷右偷,两边都不偷

class Solution { public int rob(TreeNode root) { int[] res = dfs(root); return Math.max(res[0], res[1]); } // 返回 [偷当前节点, 不偷当前节点] private int[] dfs(TreeNode node) { if (node == null) { return new int[]{0, 0}; } int[] left = dfs(node.left); int[] right = dfs(node.right); // 偷当前节点 int rob = node.val + left[1] + right[1]; // 不偷当前节点 int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); return new int[]{rob, notRob}; } }