LeetCode [337] House Robber III

 337. House Robber III

Medium

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

//C++ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> dfs(TreeNode *node) { if (node == nullptr) return {0, 0}; vector<int> rv1 = dfs(node->left); vector<int> rv2 = dfs(node->right); vector<int> rv(2, 0); rv[0] = rv1[1] + rv2[1] + node->val; rv[1] = max(rv1[0], rv1[1]) + max(rv2[0], rv2[1]); return rv; } int rob(TreeNode *root) { vector<int> rv = dfs(root); return max(rv[0], rv[1]); } }; //Java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int rob(TreeNode root) { int[] res = helper(root); return Math.max(res[0], res[1]); } int[] helper(TreeNode node){ if(node==null){ return new int[]{0,0}; } int[] l = helper(node.left); int[] r = helper(node.right); int[] res = new int[2]; res[0] = l[1] + r[1] + node.val; res[1] = Math.max(l[0],l[1]) + Math.max(r[0], r[1]); return res; } }