House Robber ||| -- LeetCode 337

[Question]

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   1

Maximum 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.

[Analysis]
This is different from previous questions in this "House Robber" series. Assume S(n) is the max amount of money the robber can get at House[n],
       S(n) = max( S(n->left)+ S(n->right),
                H[n] + S(n->left->left) + S(n->left->right) + S(n->right->left) + S(n->right->right) )

So we can use DFS to accomplish this.

[Solution]
/**
 * 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 {
    int helper(TreeNode* root, int &lsum, int &rsum) {
        if (root==NULL) return 0;
     
        int ll=0, lr=0, rl=0, rr=0;
        lsum = helper(root->left, ll, lr);
        rsum = helper(root->right, rl, rr);
        return max( lsum+rsum, root->val+ll+lr+rl+rr );
    }
public:
    int rob(TreeNode* root) {
        int lsum=0, rsum=0;
        return helper(root, lsum, rsum);
    }

};