533. Single-Value Subtrees
A botanist labels each branch junction of a plant with an integer, and the plant is stored as a binary tree root. A uniform sub-tree is a node together with all of its descendants in which every node carries exactly the same label. A single leaf is always uniform. Count how many uniform sub-trees the tree contains and return that count. Every node is the root of exactly one sub-tree, so the answer is at most the number of nodes. An empty tree contains no sub-trees, so return 0 for it.
Example 1
- Input:
- root = [2,2,2,3,2,null,4]
- Output:
- 3
- Explanation:
The three leaves 3, 2 and 4 are uniform and no larger sub-tree is, so the answer is 3.
Example 2
- Input:
- root = [7,7,7,7,7,7,7]
- Output:
- 7
- Explanation:
All seven nodes share the value 7, so each one roots a uniform sub-tree.
Example 3
- Input:
- root = [9,9,9,9,null,null,9,null,9]
- Output:
- 6
- Explanation:
Every node holds 9, so each of the 6 nodes roots a uniform sub-tree.
Constraints
0 ≤ number of nodes ≤ 500
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)