leetcode-337-House Robber III

Posted on | In , | |
Words count in article: 299 | Reading time ≈ 1

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:

1
2
3
4
5
6
7
8
9
10
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:

1
2
3
4
5
6
7
8
9
10
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int rob(TreeNode* root) 
    {
        std::pair<int, int> m = helper(root);
        return std::max(m.first, m.second);
    }
    
    std::pair<int, int> helper(TreeNode* root)
    {
        if(!root) return {0, 0};
        
        auto leftMoney = helper(root->left);
        auto rightMoney = helper(root->right);
        
        return {root->val + leftMoney.second + rightMoney.second,
                std::max(leftMoney.first, leftMoney.second) 
                + std::max(rightMoney.first, rightMoney.second)};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int[] ret = robHelper(root);
        return Math.max(ret[0], ret[1]);
    }
    
    private int[] robHelper(TreeNode root) {
        int[] ret = new int[2];
        if (root == null) return ret;
        int[] lRet = robHelper(root.left);
        int[] rRet = robHelper(root.right);
        
        ret[0] = Math.max(lRet[0], lRet[1]) + Math.max(rRet[0], rRet[1]);
        ret[1] = lRet[0] + rRet[0] + root.val;
        return ret;
    }
}
Donate? comment?