5.26 Find Leaves of Binary Tree

5.26.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 366
• Difficulty: Medium
• URL: https://leetcode.com/problems/find-leaves-of-binary-tree/
• Tags:
• Techniques: Depth First Search, Recursion, Tree

5.26.2 Description

Collect nodes layer by layer from leaves upward.

5.26.3 Solution - Height DFS

5.26.3.1 Walkthrough

Compute each node’s height measured from the nearest leaf. Leaves have height 0, and a node’s height is 1 + max(left, right). Use the height as an index into the result list to group nodes by removal round.

5.26.3.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

5.26.3.3 Code - Java

public List<List<Integer>> findLeaves(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    height(root, result);
    return result;
}

private int height(TreeNode node, List<List<Integer>> result) {
    if (node == null) {
        return -1;
    }
    int h = Math.max(height(node.left, result), height(node.right, result)) + 1;
    if (result.size() == h) {
        result.add(new ArrayList<>());
    }
    result.get(h).add(node.val);
    return h;
}