Very easy to understand recursion method


  • 0
    V

    Just translation of the problem ...

    /**
     * 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:
        int rob(TreeNode* root) {
            if (!root) return 0;
            if (!root->left && !root->right) return root->val;
            if (!root->left) return max(root->val+rob(root->right->left)+rob(root->right->right),rob(root->right));
            if (!root->right) return max(root->val+rob(root->left->left)+rob(root->left->right),rob(root->left));
            return max(root->val+rob(root->right->left)+rob(root->right->right)+rob(root->left->left)+rob(root->left->right),rob(root->left)+rob(root->right));
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.