Count Univalue Subtrees

Given the root of a binary tree, return the number of uni-value subtrees. A uni-value subtree is a subtree where every node has the same value. Pattern focus: Postorder DFS (Left Right Root). Determine whether each subtree is uniform after checking its children.

Input Format

root = binary tree root

Output Format

number of uni-value subtrees

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= node values <= 10^4
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [5,1,5,5,5,null,5]

Output:

4

Explanation:

The four leaves are uni-value subtrees.

Example 2:

Input:

root = [1,1,1,1,1,1,1]

Output:

7

Explanation:

Every subtree is uni-value when all values are equal.

Loading...
Count Univalue Subtrees - Binary Tree