Easy 4 lines C++ DFS


  • 0

    4 lines brute force, 1656ms.

        int rob(TreeNode* root) {
            return DFS(root, true);
        }
        
        int DFS(TreeNode* root, bool canRob){
            if(!root) return 0;
            int noRob = DFS(root->left, true) + DFS(root->right, true);
            return canRob ? max(root->val + DFS(root->left, false) + DFS(root->right, false), noRob) : noRob;
        }
    

    Here is a greedy one, 22ms.
    idea:
    Each node only has 2 status, be robbed or not.
    Store amount of money under 2 status into a vector<int>v(2).
    v[0]: it's not robbed.
    v[1]: it's robbed.

        int rob(TreeNode* root) {
            auto res = DFS(root);
            return max(res[0], res[1]);
        }
        
        vector<int> DFS(TreeNode* root){
            if(!root) return {0,0};
            auto left = DFS(root->left);
            auto right = DFS(root->right);
            vector<int>res(2);
            res[0] = max(left[0], left[1]) + max(right[0], right[1]);
            res[1] = root->val + left[0] + right[0];
            return res;
        }
    

Log in to reply
 

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