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
/
2Now 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].
一刷
题解：利用level信息，这个level指的是从下到上的高度。
/**
* 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>> res = new ArrayList<>();
height(root, res);
return res;
}
private int height(TreeNode node, List<List<Integer>> res){
if(node == null) return -1;
int level = 1 + Math.max(height(node.left, res), height(node.right, res));
while(res.size()<level+1) res.add(new ArrayList<>());
res.get(level).add(node.val);
return level;
}
}
二刷
思路同上
/**
* 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>> res = new ArrayList<>();
if(root == null) return res;
height(root, res);
return res;
}
private int height(TreeNode root, List<List<Integer>> res){
if(root == null) return -1;
int level = 1 + Math.max(height(root.left, res), height(root.right, res));
if(level+1>res.size()){
res.add(new ArrayList<>());
}
res.get(level).add(root.val);
return level;
}
}
三刷
根据节点的高度信息，取出对应层次的list, 并add新的val
/**
* 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<>();
height(root, res);
return res;
}
private int height(TreeNode root, List<List<Integer>> res){
if(root == null) return -1;
int left = height(root.left, res);
int right = height(root.right, res);
int height = 1 + Math.max(left, right);
while(height>=res.size()) res.add(new ArrayList<>());
res.get(height).add(root.val);
return height;
}
}
