[Leetcode] 250. Count Univalue Subtrees
Given the rootof a binary tree, return _the number of uni-value _subtrees.
A uni-value subtree means all nodes of the subtree have the same value.
Example 1:
Input: root = [5,1,5,5,5,null,5]
Output: 4
Example 2:
Input: root = []
Output: 0
Example 3:
Input: root = [5,5,5,5,5,null,5]
Output: 6
Constraints:
The number of the node in the tree will be in the range [0, 1000].
-1000 <= Node.val <= 1000
How to understand?
Uni value subtree means the subtree of the given tree, has only one value in the tree. Check each subtree and find the number of uni value subtree from the given root tree.
How to approach?
DFS
class Solution:
def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if node is None:
return True, 0
left = dfs(node.left)
right = dfs(node.right)
isLeftUniValue = left[0]
isRightUniValue = right[0]
count = left[1] + right[1]
if isLeftUniValue and isRightUniValue:
if node.left and node.val != node.left.val:
return False, count
if node.right and node.val != node.right.val:
return False, count
return True, count + 1
return False, count
return dfs(root)[1]
create dfs function that takes node as input.
and lastly return the result of the dfs function that took root node as input.
dfs function is returning the boolean and count value as tuple.
when the node is None, return the True and 0 count.
create left and right and call the dfs function with node left and right.
set boolean value with [0] value of left and right, and count is [1] value's sum.
when both boolean values are true then check if it has same value as current node value. if it doesn't have same value then it can't be the uni value sub tree at this current node so return False.
when both boolean values are true then return the true and +1 count since it means that this current node is also uni value sub tree.
if the both boolean values are not true then return false. since current node can't be uni value sub tree.