NeetCode #405LC-366MediumTreesNC Algo100
← Back to All Problems#405 · #366 · Find Leaves of Binary Tree(寻找二叉树的叶子节点)
📌 Problem Statement & Constraints
Given the root of a binary tree, collect all its nodes level by level from the leaves upward: first all leaves are removed, then the new leaves, and so on. Return the list of levels. Constraints: the number of nodes is in
[1, 100].💡 Core Algorithmic Approaches
- The level of a node equals its height, where a leaf has height 0.
- So a single post-order traversal computing heights assigns every node to its level.
- Nodes at the same height are grouped together, giving exactly the removal order.
- This is O(n) instead of simulating the removal process repeatedly.
💻 Benchmark Python3 Implementation
class Solution:
def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
def height(node: Optional[TreeNode]) -> int:
"""Height of the subtree: a leaf has height 0."""
if not node:
return -1
h = 1 + max(height(node.left), height(node.right))
while len(res) <= h: # grow the level list as needed
res.append([])
res[h].append(node.val)
return h
height(root)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(h) for the recursion stack plus O(n) for the result.
⚠️ Interview Pitfalls & Follow-ups
- Defining the leaf height as 1: then the levels would be off by one; a leaf must map to level 0.
- Repeatedly simulating the removals: O(n^2).
- Appending to
reswithout growing it first: anIndexErrorwhen the height exceeds the current length. - Assuming the tree is balanced: the height can reach n for a degenerate tree.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.