Tree with Distinct Parities

Given a binary tree root, return the number of perfect nodes. A perfect node has two properties:

• Has both children
• The sum of one subtree is even and the sum of the other subtree is odd

Constraints

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

https://binarysearch.com/problems/Tree-with-Distinct-Parities

Examples

Example 1

Input

• root =

Output

• answer = 2

Explanation

Nodes 1 and 3 meet the criteria.

Example 2

Input

• root =

Output

• answer = 0

Explanation

No node has both a left and a right child.

Solution