337. House Robber III

337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

\ 2 3 \ \

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7. Example 2:

\ 4 5 / \ \

Maximum amount of money the thief can rob = 4 + 5 = 9.

思路：

题意：不能连续抢直接相连的两个节点。即例2中，抢了3就不能抢4，5。问最多能抢好多。 给一个二叉树，求它不直接相连的节点的val和最大为多少。 如果抢了当前节点，那么它的左右孩子就肯定不能抢了。 如果没有抢当前节点，左右孩子抢不抢取决于左右孩子的孩子的val大小。

像House Robber I一样，使用动态规划法，对于每个节点，使用两个变量，res[0], res[1]，分别表示不选择当前节点子树的数值和，选择当前节点子树的数值和，动态规划的思想，然后递归。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public int rob(TreeNode root) { int[] res = robSub(root); return Math.max(res[0], res[1]); } public int[] robSub(TreeNode root){ if(root == null) return new int[2]; int[] left = robSub(root.left); int[] right = robSub(root.right); int[] res = new int[2]; res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // do not choose current node res[1] = root.val + left[0] + right[0]; // choose current node return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。