Tree - 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:

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:

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：

/**

 * 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：

/**

 * 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
}