Skip to content

366. Find Leaves of Binary Tree 👍

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  vector<vector<int>> findLeaves(TreeNode* root) {
    vector<vector<int>> ans;
    depth(root, ans);
    return ans;
  }

 private:
  // Returns the depth of the root (0-indexed).
  int depth(TreeNode* root, vector<vector<int>>& ans) {
    if (root == nullptr)
      return -1;

    const int l = depth(root->left, ans);
    const int r = depth(root->right, ans);
    const int h = 1 + max(l, r);
    if (ans.size() == h)  // Meet a leaf.
      ans.push_back({});

    ans[h].push_back(root->val);
    return h;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public List<List<Integer>> findLeaves(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    depth(root, ans);
    return ans;
  }

  // Returns the depth of the root (0-indexed).
  private int depth(TreeNode root, List<List<Integer>> ans) {
    if (root == null)
      return -1;

    final int l = depth(root.left, ans);
    final int r = depth(root.right, ans);
    final int h = 1 + Math.max(l, r);
    if (ans.size() == h) // Meet a leaf.
      ans.add(new ArrayList<>());

    ans.get(h).add(root.val);
    return h;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def findLeaves(self, root: TreeNode | None) -> list[list[int]]:
    ans = []

    def depth(root: TreeNode | None) -> int:
      """Returns the depth of the root (0-indexed)."""
      if not root:
        return -1

      l = depth(root.left)
      r = depth(root.right)
      h = 1 + max(l, r)

      if len(ans) == h:  # Meet a leaf
        ans.append([])

      ans[h].append(root.val)
      return h

    depth(root)
    return ans