Univalue Tree Count

A univalue tree is a tree where all nodes under it have the same value.

Given a binary tree root, return the number of univalue subtrees.

Constraints

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

https://binarysearch.com/problems/Univalue-Tree-Count

Examples

Example 1

Input

• root =

Output

• answer = 2

Explanation

The two leaf nodes are unival trees.

Example 2

Input

• root =

Output

• answer = 5

Explanation

The unival trees include four leaf nodes (three of them are 1s, the other one is the rightmost 0), and one subtree in the middle (containing all 1s).

Solution