C++ DP&DFS O(n) time


  • 0
    Z

    C++, DP&post-order traversal DFS, O(n) time
    The reward from the sub tree include the current node is the larger of (i) sum of rewards from left and right child trees and (ii) sum of current node's value + sum of rewards of the children of left child node and right child node (excluding the values of the the left and right child nodes).

    class Solution {
    public:
        int rob(TreeNode* root) {
            vector<int> vc=robber(root);
            return vc[0];
        }
        
        vector<int> robber(TreeNode* root){
            vector<int> vc={0,0}, vl, vr;
            if(!root)   return vc;
            vl=robber(root->left);
            vr=robber(root->right);
            vc[1]=vl[0]+vr[0];
            vc[0]=vc[1]<vl[1]+vr[1]+root->val?vl[1]+vr[1]+root->val:vc[1];
            return vc;
        }
        
    };
    

Log in to reply
 

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