建设网站要注册公司吗,做网站网页挣钱不,网站设计建设公司,南宁建站模板源码// 很好的一道题目#xff0c;既考察递归又考察动归
// 这个版本超时了#xff0c;原因是暴搜
// 很显然这里使用的是前序#xff0c;那是不是应该考虑后序#xff1f;public int rob(TreeNode root) {if (root null) {return 0;}if (root.left null root.rig…// 很好的一道题目既考察递归又考察动归
// 这个版本超时了原因是暴搜
// 很显然这里使用的是前序那是不是应该考虑后序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;}
