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:
代码语言：javascript复制Input: [3,2,3,null,3,null,1]
3
/
2 3
3 1
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 3 1 = **7**.Example 2:
代码语言：javascript复制Input: [3,4,5,1,3,null,1]
3
/
4 5
/
1 3 1
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 5 = **9**.思路：
这是偷房子的第三题，要求就是偷了父节点就不能偷子节点，考点就是后序遍历，访问节点的时候，根据子节点的结果，决定偷和不偷，依次递归返回。
代码：
java：
代码语言：javascript复制/**
* 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]);
}
private 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]);
res[1] = root.val left[0] right[0];
return res;
}
}go：
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
var rob, norob int
if root != nil {
rob, norob = recursion(root)
}
return max(rob, norob)
}
// return rob, onrob
func recursion(node *TreeNode) (rob, norob int) {
if node == nil {
return
}
lrob, lnorob := recursion(node.Left)
rrob, rnorob := recursion(node.Right)
rob = node.Val lnorob rnorob
norob = max(lrob, lnorob) max(rrob, rnorob)
return
}
func max(i, j int) int {
if i > j {
return i
}
return j
}
