My 12ms C++ solution


  • 5
    L
     int rob(TreeNode* node, int& lm, int& rm) {
        if (!node)  return 0;
        int lm1 = 0, lm2 = 0, rm1 = 0, rm2 = 0;
        
        lm = rob(node->left, lm1, rm1);
        rm = rob(node->right, lm2, rm2);
        
        return max(node->val + lm1 + rm1 + lm2 + rm2, lm + rm);
      }
    
     int rob(TreeNode* root) {
        int res = 0;
        int lm = 0, rm = 0;
        res = rob(root, lm, rm);
        return res;
     }
    
    • lm is the max rob value of node->left
    • rm is the max rob value of node->right
    • lm1 is the max rob value of node->left->left (Same as lm2)
    • rm1 is the max rob value of node->left->right (Same as rm2)
    • So the max rob value of node is the max value between (lm + rm) and (node->val + lm1 + lm2 + rm1 + rm2)

Log in to reply
 

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