Solution
Approach 1: Depth First Search
Intuition
Given a node in our tree, we know that it is a univalue subtree if it meets one of the following criteria:
 The node has no children (base case)
 All of the node's children are univalue subtrees, and the node and its children all have the same value
With this in mind we can perform a depthfirstsearch on our tree, and test if each subtree is univalue in a bottomup manner.
!?!../Documents/250_Count_Univalue_SUbtrees.json:1000,518!?!
Algorithm
Complexity Analysis

Time complexity : .
Due to the algorithm's depthfirst nature, the
is_uni
status of each node is computed from bottom up. When given theis_uni
status of its children, computing theis_uni
status of a node occurs inThis gives us time for each node in the tree with total nodes for a time complexity of

Space complexity : , with
H
being the height of the tree. Each recursive call ofis_uni
requires stack space. Since we fully processis_uni(node.left)
before callingis_uni(node.right)
, the recursive stack is bound by the longest path from the root to a leaf  in other words the height of the tree.
Approach 2: Depth First Search  Pass Parent Values
Algorithm
We can use the intuition from approach one to further simplify our algorithm. Instead of checking if a node has no children, we treat null
values as univalue subtrees that we don't add to the count.
In this manner, if a node has a null
child, that child is automatically considered to a valid subtree, which results in the algorithm only checking if other children are invalid.
Finally, the helper function checks if the current node is a valid subtree but returns a boolean indicating if it is a valid component for its parent. This is done by passing in the value of the parent node.
The above code is a commented version of the code here, originally written by Stefan Pochmann.
Complexity Analysis

Time complexity : . Same as the previous approach.

Space complexity : , with
H
being the height of the tree. Same as the previous approach.
Written by @alwinpeng.