Share my c++ DP solution


  • 0
    H

    The idea is same as House Robber II (dp[n] = max(dp[n+1], dp[n+2]+v[n] ). When you decide whether you rob a house, you need its child solution and child's child solution. res[0] is root's solution, res[1] is root's left child solution, res[2] is root's right child solution. DP function is res[0] = max(L[0]+R[0],L[1]+L[2]+R[1]+R[2]+now->val);

    class Solution {
    public:
        vector<int> dp(TreeNode* now)
        {
            vector<int> res(3);
            if(now==NULL)
                return res;
            vector<int> L = dp(now->left);
            vector<int> R = dp(now->right);
            res[0] = max(L[0]+R[0],L[1]+L[2]+R[1]+R[2]+now->val);
            res[1] = L[0];
            res[2] = R[0];
            return res;
        }
        int rob(TreeNode* root) {
            vector<int> result = dp(root);
            return result[0];
        }
    };
    

Log in to reply
 

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