Leetcode Problem 250. Count Univalue Subtrees

250. Count Univalue Subtrees

Leetcode Solutions

Depth First Search to Count Uni-value Subtrees

  1. Define a helper function dfs that takes a node as an argument and returns a tuple (is_uni, count), where is_uni is a boolean indicating if the subtree rooted at the node is a uni-value subtree, and count is the number of uni-value subtrees within that subtree.
  2. If the node is null, return (True, 0) since a null node is trivially a uni-value subtree and contributes 0 to the count.
  3. Recursively call dfs on the left and right children of the node.
  4. Check if the left and right subtrees are uni-value subtrees and if their values match the current node's value (if they exist).
  5. If both subtrees are uni-value and their values match the current node's value, the current subtree is also a uni-value subtree. Increment the count and return (True, count).
  6. If either subtree is not a uni-value subtree or their values do not match the current node's value, the current subtree is not a uni-value subtree. Return (False, count) without incrementing.
  7. The final count of uni-value subtrees is obtained by calling dfs(root) and taking the second element of the returned tuple.
UML Thumbnail

Depth First Search with Global Variable

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...