House Robber III — LeetCode 337 Python Solution

The problem

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Example

Input

root = [3,2,3,null,3,null,1]

Output

7

Explanation

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Python solution

# 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 dfs(root: Optional[TreeNode]) -> (int, int):
            if root is None:
                return 0, 0
            la, lb = dfs(root.left)
            ra, rb = dfs(root.right)
            return root.val + lb + rb, max(la, lb) + max(ra, rb)

        return max(dfs(root))

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 337. House Robber III is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems