Question
Formatted question description: https://leetcode.ca/all/366.html
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:
Input: [1,2,3,4,5]
1
/ \
2 3
/ \
4 5
Output: [[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:
[]
@tag-tree
Algorithm
Each node is separated from the left child node and the right child node to get two depths,
Since the condition of becoming a leaf node is that the left and right child nodes are empty, we take the larger value of the left and right child nodes plus 1 as the depth value of the current node.
Knowing the depth value, you can add the node value to the correct position in the result.
Code
Java
import java.util.ArrayList;
import java.util.List;
public class Find_Leaves_of_Binary_Tree {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
helper(result, root);
return result;
}
// traverse the tree bottom-up recursively
private int helper(List<List<Integer>> list, TreeNode root) {
if (root == null) {
return -1; // @note: +1==0, mapping to list index
}
int left = helper(list, root.left);
int right = helper(list, root.right);
int currentDepthFromBottom = Math.max(left, right) + 1;
// the first time this code is reached is when curr==0,
// since the tree is bottom-up processed.
if (list.size() <= currentDepthFromBottom) {
list.add(new ArrayList<Integer>());
}
list.get(currentDepthFromBottom).add(root.val);
return currentDepthFromBottom;
}
}