Leetcode Problem 1273. Delete Tree Nodes

1273. Delete Tree Nodes

Leetcode Solutions

DFS with Post-order Traversal

  1. Create a graph representation of the tree using adjacency lists.
  2. Define a recursive DFS function that takes the current node index as an argument.
  3. Initialize a sum variable to the value of the current node.
  4. Initialize a count variable to 1 (to count the current node).
  5. Iterate over the children of the current node.
  6. For each child, call the DFS function recursively and obtain the sum and count of the subtree rooted at that child.
  7. Add the child's sum to the current sum and the child's count to the current count.
  8. If the sum of the subtree rooted at the current node is zero, set the count to zero (exclude the subtree).
  9. Return the sum and count of the subtree rooted at the current node.
  10. Call the DFS function starting from the root node (index 0).
  11. Return the count obtained from the DFS call.
UML Thumbnail

Iterative Post-order Traversal with Stack

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...