0%

Leetcode366-findLeavesOfBinaryTree

Description

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

1
2
3
4
5
6
7
8
9
Input: [1,2,3,4,5]

1
/ \
2 3
/ \
4 5

Output: [[4,5,3],[2],[1]]

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();

traversal(root, res);

return res;
}

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