https://leetcode.com/problems/house-robber-iii/

1. Use recursion:

  1. //8 ms    18.4 MB
  3. /**
  4.  * Definition for a binary tree node.
  5.  * struct TreeNode {
  6.  *     int val;
  7.  *     TreeNode *left;
  8.  *     TreeNode *right;
  9.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int rob(TreeNode* root) {
  15.         int l = 0;
  16.         int r = 0;
  18.         return rob(root, l, r);
  19.     }
  21. private: 
  22.     int rob(TreeNode* root, int& l, int& r){
  23.         if(!root) return 0;
  25.         int ll = 0;
  26.         int lr = 0;
  27.         int rl = 0;
  28.         int rr = 0;
  30.         l = rob(root->left, ll, lr);
  31.         r = rob(root->right, rl, rr);    
  33.         return max(root->val + ll + lr + rl + rr, l + r);
  34.     }
  35. };