⚡Flashcard Drill➔
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

  1. The level of a node equals its height, where a leaf has height 0.
  2. So a single post-order traversal computing heights assigns every node to its level.
  3. Nodes at the same height are grouped together, giving exactly the removal order.
  4. 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 res without growing it first: an IndexError when 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems