[LintCode/LeetCode] House Robber III

macg0406 發(fā)布于2019-08-14 15:34 / 1166人閱讀

摘要：解法真的非常巧妙，不過這道題里仍要注意兩個細(xì)節(jié)。中，為時，返回長度為的空數(shù)組建立結(jié)果數(shù)組時，是包括根節(jié)點的情況，是不包含根節(jié)點的情況。而非按左右子樹來進(jìn)行劃分的。

Problem

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

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

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

Note

DFS解法真的非常巧妙，不過這道題里仍要注意兩個細(xì)節(jié)。
DFS中，root為null時，返回長度為2的空數(shù)組；
建立結(jié)果數(shù)組A時，A[0]是包括根節(jié)點的情況，A[1]是不包含根節(jié)點的情況。而非按左右子樹來進(jìn)行劃分的。

Solution

public class Solution {
    public int houseRobber3(TreeNode root) {
        int[] A = dfs(root);
        return Math.max(A[0], A[1]);
    }
    public int[] dfs(TreeNode root) {
        if (root == null) return new int[2];
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        int[] A = new int[2];
        A[0] = left[1] + root.val + right[1];
        A[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return A;
    }
}