// 很好的一道题目,既考察递归又考察动归
// 这个版本超时了,原因是暴搜
// 很显然这里使用的是前序,那是不是应该考虑后序?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;}