LeetCode337. 打家劫舍III

// 很好的一道题目，既考察递归又考察动归
// 这个版本超时了，原因是暴搜
// 很显然这里使用的是前序，那是不是应该考虑后序？public int rob(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return root.val;}if (root.left != null && root.right != null) {return Math.max(rob(root.left) + rob(root.right), root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right));}if (root.left != null) {return Math.max(rob(root.left) + rob(root.right), root.val + rob(root.left.left) + rob(root.left.right));}return Math.max(rob(root.left) + rob(root.right), root.val + rob(root.right.left) + rob(root.right.right));}

上面的代码其实非常的丑陋，就算暴搜也不应该这样写，而是这样

public int rob(TreeNode root) {if (root == null)return 0;int money = root.val;if (root.left != null) {money += rob(root.left.left) + rob(root.left.right);}if (root.right != null) {money += rob(root.right.left) + rob(root.right.right);}return Math.max(money, rob(root.left) + rob(root.right));}

但这题说到底是树形DP题目，最优解法应该是使用DP，如下

    public int rob(TreeNode root) {int[] res = robHelper(root);return Math.max(res[0], res[1]); }private int[] robHelper(TreeNode root) {int[] res = new int[2];if (root == null) {return res;}int[] left = robHelper(root.left);int[] right = robHelper(root.right);// 重点：root不偷，下面的结点一定都是偷吗// 分为左右结点，像case1:2偷值为2，不偷为3// 如果root不偷，下面的左右都偷反而不一定是最大值// root不偷，下面的结点有偷与不偷的权利，根据利益最大化选择偷与不偷// 但root偷，下面的结点一定不能偷// res[0] = left[1] + right[1];res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);res[1] = root.val + left[0] + right[0];return res;}