C++ bottom-up dp solution


  • 0
    M
    /**
     * 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 {
    private:
        pair<int, int> robHelper (TreeNode* root) {
            if (!root->left && !root->right) {
                return make_pair(root->val, 0);
            }
            pair<int, int> left = (root->left) ? robHelper(root->left) : make_pair(0, 0);
            pair<int, int> right = (root->right) ? robHelper(root->right) : make_pair(0, 0);
            int x = root->val + left.second + right.second; // self
            int y = max(left.first, left.second) + max(right.first, right.second);
            return make_pair(x, y);
        }
    public:
        int rob(TreeNode* root) {
            if (!root) {
                return 0;
            }
            pair<int, int> result = robHelper(root);
            return max(result.first, result.second);
        }
    };
    

Log in to reply
 

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