707. House Robber III
0
Medium
A thief has discovered a new area for his criminal activities. This area consists of houses arranged in a binary tree structure, with a single entrance called the root.
Each house, except for the root, has exactly one parent house. The thief has realized that if two directly-connected houses are robbed on the same night, the police will be alerted.
Given the root of the binary tree, the task is to determine the maximum amount of money the thief can steal without triggering the police.
Input Format
The binary tree is represented as a string input, where each node is described as "root left-child right-child". The nodes are separated by spaces, and 'N' represents a null node.
Output Format
Print the maximum amount of money the thief can steal without alerting the police.
Example
Input
3 4 5 1 3 N 1
Output
9
Constraints
The number of nodes in the binary tree is between 1 and 10^4, inclusive. The value of each node is between 0 and 10^4, inclusive.
Loading...
View Submissions
Console