问题描述
在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。
示例 1:
输入:[3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释:小偷一晚能够盗取的最高金额 = 3 3 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释:小偷一晚能够盗取的最高金额=4 5=9.
动态规划解决
前面我们刚讲过《》和《》,今天这题和之前讲的这两道题完全不同,因为前面两题所偷窃的房屋都是数组,而这题是一个二叉树。但这道题也可以使用动态规划来解决。
对于二叉树的每一个节点都有两种状态,一种是偷,一种是不偷。我们定义一个长度为2的数组dp,其中dp[0]表示不偷当前这个节点所能偷窃的最高金额,dp[1]表示偷当前节点所能偷窃的最高金额。
我们就从根节点开始遍历这棵二叉树。
如果偷根节点,那么就不能偷根节点的两个子节点,所以
dp[1]=root.val left.dp[0] right.dp[0];
这里的伪代码left.dp[0]表示的是不能偷当前节点的左子节点
如果不偷根节点,那么我们可以偷子节点也可以不偷子节点,我们取最大值即可,所以
dp[0]=max(left.dp[0],left.dp[1]) max(right.dp[0],right.dp[1]);
那么边界条件是什么呢,就是节点为空的时候,直接返回0即可。
有了递推公式和边界条件,我们来看下最终代码
public int rob(TreeNode root) {
int[] robHelp = robHelper(root);
//取偷根节点和不偷根节点的最大值
return Math.max(robHelp[1], robHelp[0]);
}
public int[] robHelper(TreeNode root) {
//边界条件
if (root == null)
return new int[2];
//这里的left是个长度为2的一维数组,其中left[0]表示不偷root.left节点
//所能偷窃的最大金额,left[1]表示偷root.left节点所能偷窃的最大金额。
int[] left = robHelper(root.left);
//right节点同left
int[] right = robHelper(root.right);
//Math.max(right[0], right[1]), root.val left[0] right[0]表示
//的是不能偷当前节点,所以可以偷两个子节点,也可以不偷子节点,我们取最大的。
//root.val left[1] right[1]表示的是偷当前节点,所以不能偷两个子节点。
return new int[]{Math.max(left[0], left[1])
Math.max(right[0], right[1]), root.val left[0] right[0]};
}
总结
如果对二叉树的遍历方式比较熟悉的话,上面代码一看就知道,他和二叉树的后续遍历非常相似,是完全从下到上的一种遍历方式,每一个节点都记录了两种状态,一种是偷,一种是不偷。每次从下往上走的时候这两种状态都会记录下来……一直到根节点,最后我们只需要返回偷根节点和不偷根节点的最大值即可。
Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved