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:
3 / 2 3 \ \ 3 1Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ 4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9./**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var rob = function(root) {
if(!root || root.length === 0) return 0;
var ret = getMax(root);
return Math.max(ret.curr, ret.child);
function getMax(node){
var left = {curr: 0, child: 0};
if(node.left !== null){
left = getMax(node.left);
}
var right = {curr: 0, child: 0};
if(node.right !== null){
right = getMax(node.right);
}
return {
curr: node.val + left.child + right.child,
child: Math.max(left.curr, left.child)
+ Math.max(right.curr, right.child)
};
}
};
[LeetCode][JavaScript]House Robber III
原文：http://www.cnblogs.com/Liok3187/p/5296669.html