Medium

Quiz

#337 House Robber III

APPROACH

A thief has found a neighborhood where the only entrance is at the root.

Every house has exactly one parent house, and all houses form a binary tree. Two directly-linked houses cannot both be robbed on the same night or the alarm triggers.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:

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

Output: 7

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

Example 2:

Input: root = [3,4,5,1,3,null,1]

Output: 9

Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

1 of 4

1:00

What is the optimal approach for this problem?