Skip to content

337. House Robber III 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct T {
  int robRoot;
  int notRobRoot;
};

class Solution {
 public:
  int rob(TreeNode* root) {
    const auto& [robRoot, notRobRoot] = robOrNotRob(root);
    return max(robRoot, notRobRoot);
  }

 private:
  T robOrNotRob(TreeNode* root) {
    if (root == nullptr)
      return {0, 0};
    const T l = robOrNotRob(root->left);
    const T r = robOrNotRob(root->right);
    return {root->val + l.notRobRoot + r.notRobRoot,
            max(l.robRoot, l.notRobRoot) + max(r.robRoot, r.notRobRoot)};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class T {
  public int robRoot;
  public int notRobRoot;
  public T(int robRoot, int notRobRoot) {
    this.robRoot = robRoot;
    this.notRobRoot = notRobRoot;
  }
}

class Solution {
  public int rob(TreeNode root) {
    T t = robOrNotRob(root);
    return Math.max(t.robRoot, t.notRobRoot);
  }

  private T robOrNotRob(TreeNode root) {
    if (root == null)
      return new T(0, 0);
    T l = robOrNotRob(root.left);
    T r = robOrNotRob(root.right);
    return new T(root.val + l.notRobRoot + r.notRobRoot,
                 Math.max(l.robRoot, l.notRobRoot) + Math.max(r.robRoot, r.notRobRoot));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def rob(self, root: TreeNode | None) -> int:
    def robOrNot(root: TreeNode | None) -> tuple:
      if not root:
        return (0, 0)

      robLeft, notRobLeft = robOrNot(root.left)
      robRight, notRobRight = robOrNot(root.right)

      return (root.val + notRobLeft + notRobRight,
              max(robLeft, notRobLeft) + max(robRight, notRobRight))

    return max(robOrNot(root))