Leetcode Problem 1519. Number of Nodes in the Sub-Tree With the Same Label

1519. Number of Nodes in the Sub-Tree With the Same Label

Leetcode Solutions

Depth First Search (DFS) Approach

  1. Create an adjacency list from the given edges to represent the tree.
  2. Initialize an array ans of size n to store the result for each node.
  3. Define a recursive function dfs that takes the current node and its parent as arguments.
  4. Inside dfs, initialize a 26-length array count to keep track of the label counts in the subtree.
  5. Set count[labels[node] - 'a'] to 1 since the node itself should be counted.
  6. For each child of the current node, if the child is not the parent, recursively call dfs on the child.
  7. After visiting a child, add the counts from the child's subtree to the current node's count array.
  8. After visiting all children, set ans[node] to the count of the node's label.
  9. Return the count array from the dfs function.
  10. Call dfs starting from the root node (0) with no parent (-1).
  11. Return the ans array.
UML Thumbnail

Breadth First Search (BFS) Approach

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...