Leetcode

House Robber III

  • Time:O(n)
  • Space:O(n)

C++

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)
      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)};
  }
};

JAVA

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));
  }
}

Python

class Solution:
  def rob(self, root: Optional[TreeNode]) -> int:
    def robOrNot(root: Optional[TreeNode]) -> 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))