-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0337 [M] House Robber III
Code with Senpai edited this page Jun 8, 2022
·
3 revisions
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def postorder(root):
if not root:
return [0, 0]
L = postorder(root.left) # left subtree's [with_root, without_root] pair
R = postorder(root.right) # right subtree's [with_root, without_root] pair
with_root = root.val + L[1] + R[1] # we can't take adjacent, only withoutRoot
without_root = max(L) + max(R) # we have options to skip and choose, withRoot or withoutRoot
return [with_root, without_root]
return max(postorder(root))
footer