1201. Maximum Independent Set on Tree

Given a binary tree (level-order with null for missing nodes), an independent set is a set of nodes with no two connected by an edge (no parent-child pair). Return the maximum number of nodes in such a set. The input is JSON {tree}.

Input: JSON {tree}.

Output: Integer — the size of the maximum independent set.

Examples

Input: {"tree":[1,2,3]}
Output: 2
Explanation: Choose the two children.

Input: {"tree":[1,2,null,3]}
Output: 2
Explanation: Choose the root and grandchild.

Input: {"tree":[1]}
Output: 1
Explanation: Single node.

Constraints

• 1<=nodes<=10^4

Asked by