337.md

鹅归法重出江湖！

之后再附上一个别人的解答，两个参数的递归避免了互相调用TLE，也就不用鹅归了

不用两个参数的话，返回多个值也是可以的哦

/**
 * 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 {
    // answer mark
    map<TreeNode*, int> m1, m2;
    // select root node
    int help1(TreeNode* root){
        if(root == NULL) return 0;
        if(m1.find(root) != m1.end()) return m1[root];
        int ans = root->val;
        if(root->left != NULL) ans+= help2(root->left);
        if(root->right != NULL) ans+= help2(root->right);
        m1[root] = ans;
        return ans;
    }
    
    // dont select root node
    int help2(TreeNode* root){
        if(root == NULL) return 0;
        if(m2.find(root) != m2.end()) return m2[root];
        int ans = 0;
        if(root->left != NULL) ans+= max(help1(root->left) ,help2(root->left));
        if(root->right != NULL) ans+= max(help1(root->right) ,help2(root->right));
        m2[root] = ans;
        return ans;
    }
public:
    int rob(TreeNode* root) {
        return max(help1(root), help2(root));
    }
};

下面是discuss的解答

static int max(int a, int b) {
    return a > b ? a : b;
}
 
static void maxMoney(struct TreeNode* root, int *withMe, int *withoutMe) {
    int wMeL, woMeL; // max money robbed: (with/without me for left child)
    int wMeR, woMeR; // max money robbed: (with/without me for right child)
    
    if (!root)
        return;
    wMeL = woMeL = wMeR = woMeR = 0;
    maxMoney(root->left, &wMeL, &woMeL);
    maxMoney(root->right, &wMeR, &woMeR);
    *withMe = woMeL + woMeR + root->val;
    *withoutMe = max(wMeL, woMeL) + max(wMeR, woMeR);
}
 
int rob(struct TreeNode* root) {
    int withMe, withoutMe;

    withMe = withoutMe = 0;
    maxMoney(root, &withMe, &withoutMe);
    return max(withMe, withoutMe);
}