[LeetCode] 366. Find Leaves of Binary Tree

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:
Given binary tree 

          1
         / \
        2   3
       / \     
      4   5    

Returns [4, 5, 3], [2], [1].

Explanation:

1. Removing the leaves [4, 5, 3] would result in this tree:

          1
         / 
        2          

2. Now removing the leaf [2] would result in this tree:

          1          

3. Now removing the leaf [1] would result in the empty tree:

          []         

Returns [4, 5, 3], [2], [1].

Thought process:

The question asks us to "collect a tree's nodes as if you were doing this: collect and remove all leaves, repeat until the tree is empty". So we don't actually remove the leaves. Instead, we add a node to its correct list by calculating its height.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> findLeaves(TreeNode root) { List<List<Integer>> leaves = new ArrayList<>(); findLeavesByHeight(root, leaves); return leaves; } private int findLeavesByHeight(TreeNode root, List<List<Integer>> leaves) { if (root == null) { return -1; } int height = Math.max(findLeavesByHeight(root.left, leaves), findLeavesByHeight(root.right, leaves)) + 1; if (leaves.size() <= height) { leaves.add(new ArrayList<>()); } leaves.get(height).add(root.val); return height; } }

Time complexity:
Say n = number of nodes, the time complexity is O(n).