Find Leaves of Binary Tree
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:
- Removing the leaves [4, 5, 3] would result in this tree:
1
/
2
- Now removing the leaf [2] would result in this tree:
1
- Now removing the leaf [1] would result in the empty tree:
[]
Returns [4, 5, 3], [2], [1].
/**
* 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>> result = new ArrayList<>();
if (root == null) {
return result;
}
findLeavesHelper(root, result);
return result;
}
private int findLeavesHelper(TreeNode root, List<List<Integer>> result) {
if (root == null) {
return -1;
}
int leftLevel = findLeavesHelper(root.left, result);
int rightLevel = findLeavesHelper(root.right, result);
int level = Math.max(leftLevel, rightLevel) + 1;
if (result.size() == level) {
result.add(new ArrayList<>());
}
result.get(level).add(root.val);
root.left = root.right = null;
return level;
}
}
Hope this helps,
Michael