Count Univalue Subtrees

Given a binary tree, determine the number of subtrees that are univalue. A univalue subtree is a subtree where all nodes within that subtree have the same value. This problem is fundamental to understanding tree traversal and recursive problem-solving.

Problem Description

You are tasked with writing a function that takes the root of a binary tree as input and returns the total count of univalue subtrees within it.

Key Requirements:

• A single node is considered a univalue subtree.
• An empty tree (or a null root) contains zero univalue subtrees.
• You need to traverse the entire tree to identify all possible subtrees and check if they are univalue.

Expected Behavior:

Your function should return an integer representing the total count of univalue subtrees.

Edge Cases:

• An empty tree.
• A tree with only one node.
• A tree where all nodes have the same value.
• A tree where no subtrees (other than single nodes) are univalue.

Examples

Example 1:

Input:
    5
   / \
  1   5
 / \   \
5   5   5

Output: 4

Explanation:
The following are univalue subtrees:
1. The left child node with value 5.
2. The right child node with value 5.
3. The node with value 1 and its two children (both 5), which is NOT a univalue subtree because 1 != 5.
4. The subtree rooted at the left child of 5 (value 1) is NOT univalue.
5. The subtree rooted at the right child of 5 (value 5) IS univalue.
6. The subtree rooted at the root (value 5) IS univalue.
7. The single nodes themselves are univalue subtrees.
   - Node 5 (root)
   - Node 1 (left child)
   - Node 5 (right child of root)
   - Node 5 (left child of 1)
   - Node 5 (right child of 1)
   - Node 5 (right child of right child of root)

Correcting the explanation to reflect the problem:
The univalue subtrees are:
1. The leaf node with value 5 (left child of the node with value 1).
2. The leaf node with value 5 (right child of the node with value 1).
3. The leaf node with value 5 (right child of the node with value 5).
4. The subtree rooted at the node with value 1, which has children with value 5. This is NOT a univalue subtree because 1 != 5.
5. The subtree rooted at the node with value 5 (right child of the root). Its left child is null, and its right child is a leaf node 5. This IS a univalue subtree.
6. The subtree rooted at the root node (value 5). Its left child is a subtree rooted at 1, and its right child is a subtree rooted at 5. Since the left subtree is not univalue, the entire tree is not univalue.
Wait, the definition is "all nodes within that subtree".
Let's re-evaluate the first example:
    5
   / \
  1   5
 / \   \
5   5   5

Univalue Subtrees:
1. Leaf node 5 (left child of 1)
2. Leaf node 5 (right child of 1)
3. Leaf node 5 (right child of the right child of root)
4. The subtree rooted at node 1. Its children are 5 and 5. Since the root is 1 and its children are 5, this is NOT a univalue subtree.
5. The subtree rooted at the right child of the root (value 5). Its right child is a leaf 5. All nodes in this subtree are 5. This IS a univalue subtree.
6. The subtree rooted at the root (value 5). Its left child is rooted at 1, and its right child is rooted at 5. Since the left subtree is not univalue, the whole tree is not univalue.

The single nodes are always univalue subtrees.
1. Root (5) - not a univalue subtree as its children are different values.
2. Left child of root (1) - not a univalue subtree as its children are 5.
3. Right child of root (5) - UNIVALUE. Its only non-null child is a leaf 5.
4. Left child of 1 (5) - UNIVALUE (leaf).
5. Right child of 1 (5) - UNIVALUE (leaf).
6. Right child of right child of root (5) - UNIVALUE (leaf).

The univalue subtrees are:
- The right child of the root (value 5) and its right leaf child (value 5). (This entire subtree has value 5)
- The three leaf nodes with value 5.

Total: 4. The univalue subtrees are:
- The leaf node with value 5 (left child of node 1).
- The leaf node with value 5 (right child of node 1).
- The leaf node with value 5 (right child of node 5).
- The subtree rooted at the node with value 5 (which is the right child of the root node). This subtree consists of the node with value 5 and its right child which is a leaf node with value 5.

Example 2:

Input:
    5
   / \
  5   5
 / \   \
5   5   5

Output: 6

Explanation:
In this tree, every node is 5. Therefore, every subtree is a univalue subtree.
- The three leaf nodes are univalue.
- The two nodes with two children are univalue.
- The root node is univalue.
Total univalue subtrees: 3 (leaves) + 2 (intermediate) + 1 (root) = 6.

Example 3:

Input:
    5
   /
  1

Output: 2

Explanation:
1. The leaf node with value 1 is a univalue subtree.
2. The root node with value 5 is a univalue subtree.
The subtree rooted at 5, which has a left child 1, is not a univalue subtree.

Constraints

• The number of nodes in the tree will be between 0 and 1000.
• Node values will be integers between -1000 and 1000.
• The tree is a standard binary tree (each node has at most two children).
• Your solution should aim for an efficient time complexity, ideally O(N) where N is the number of nodes.

Notes

• Consider using a recursive approach (like Depth First Search) to traverse the tree.
• You might need to pass information up from child nodes to parent nodes during the traversal to determine if a subtree is univalue.
• Think about how to combine the results from the left and right subtrees to make a decision for the current node.
• A helper function that returns both whether a subtree is univalue AND the count of univalue subtrees within it might be useful.