My accepted solution, much cleaner


  • 1
    P
    class Solution {
    public:
      /*
          a
         / \
        b   c
    
      Consider above case, at leaf
      rob_with_root = root_val+max_left_wo_root + max_right_wo_root
      rob_without_root = max(max_left_with_root, max_left_wo_root) +
                         max(max_right_with_root, max_right_wo_root)
      max_rob = std::max(rob_with_root, rob_without_root);
      */
    
      void dp(TreeNode* root, int& rob_with_root, int& rob_without_root) {
        if (nullptr == root) {
          rob_with_root = 0;
          rob_without_root = 0;
          return;
        }
        int max_left_wo_root=0;
        int max_right_wo_root=0;
    
        int max_left_with_root=0;
        int max_right_with_root=0;
    
        dp(root->left, max_left_with_root, max_left_wo_root);
        dp(root->right, max_right_with_root, max_right_wo_root);
    
        rob_with_root = root->val + max_left_wo_root + max_right_wo_root;
        rob_without_root = std::max(max_left_with_root, max_left_wo_root) +
                           std::max(max_right_with_root, max_right_wo_root);
      }
      int rob(TreeNode* root) {
        int root_val=0;
        int children_val=0;
        dp(root, root_val, children_val);
        return std::max(root_val, children_val);
      }
    };

Log in to reply
 

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