Partition Tree

Given the root to a binary tree root, return a list of two numbers where the first number is the number of leaves in the tree and the second number is the number of internal (non-leaf) nodes.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Partition-Tree

Examples

Example 1

Input

• root =

Output

• answer = [2, 1]

Explanation

This tree has 2 leaves and 1 internal node.

Solution