FindLeavesOfBinaryTree [source code]
public class FindLeavesOfBinaryTree {
static
/******************************************************************************/
public class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
dfs(res, root);
return res;
}
public int dfs(List<List<Integer>> levels, TreeNode root) {
if (root == null) return 0;
int left = dfs(levels, root.left);
int right = dfs(levels, root.right);
int dist = Math.max(left, right) + 1;
if (levels.size() < dist) {
List<Integer> level = new ArrayList<>();
level.add(root.val);
levels.add(level);
} else {
List<Integer> level = levels.get(dist - 1);
level.add(root.val);
}
return dist;
}
}
/******************************************************************************/
public static void main(String[] args) {
FindLeavesOfBinaryTree.Solution tester = new FindLeavesOfBinaryTree.Solution();
}
}
这题首先笨办法是很简单的, 就是一个while(tree.size > 1)这样的循环下面, 每一个iteration来一个DFS就行了, 但是这样最后的time就非常差, 应该是lgN * N;
比较理想的解估计是直接一个DFS就能做完; 先看看能不能想到这个解法;
这一题的DFS必须要PostOrder;
这个题目整体最后想到的办法还是很简单的, 其实这个题目就是一个最pure的用recursion来做的题目; 我们当初第一次做depth的题目的时候, 还觉得那个题目对于recursion的使用不够直接; 这里这个就真的够直接了, 因为leaf就直接是对应(返回)的0, 然后每一个node的返回值, 都可以直接根据自己的两个child的返回值直接计算, 不需要任何的tag或者accum;
至于细节的逻辑就没有什么特别好说的了; recursion内部的处理其实就是一个判断当前的leaf level对应的list是否已经被init. 如果没有, 就需要初始化一下; 这个问题只要你遵守PostOrder, 那么就很好处理, 不会出现跳level, 也就是说比如我们levels里面现在只有最底下的对应返回值是1的这一层的list, 结果你突然就跑到了3的这一层这样的情况; 只要你是PostOrder, 或者是InOrder好像也行, 那么当你走到一个level的时候, 你就可以确定下面的level的对应的list肯定全部已经被init, 你自己当前所在的level的list如果还没有被初始化, 那么现在的levels的size肯定是dist - 1.
本来一个想法是让leaf(左右child都是Null的判断)的dist作为0的, 但是后来想想这样Null自己的值就不太好处理(其实如果也作为0或者作为-1也是可以的, 因为这里算的是-1), 所以干脆就用1了; 这样最后dist是1的对应的list在levels里面的index就是0, -1操作一下就行了, 也不是什么很大的问题;
最后的速度是1ms (21%), 其实是submission最优解了;
这个是discussion里面看到的:
For this question we need to take bottom-up approach. The key is to find the height of each node. Here the definition of height is:
The height of a node is the number of edges from the node to the deepest leaf. --CMU 15-121 Binary Trees
I used a helper function to return the height of current node. According to the definition, the height of leaf is 0. h(node) = 1 + max(h(node.left), h(node.right)).
The height of a node is also the its index in the result list (res). For example, leaves, whose heights are 0, are stored in res[0]. Once we find the height of a node, we can put it directly into the result.
底下好像有人讨论, 真正面试的时候除了返回这个list, 你是否需要modify这个input, 也就是给你的这个tree, 最后就是要被你摘的啥也不剩;
这个是在我的逻辑的基础上稍微优化了一下:
private int findLeavesHelper(List<List<Integer>> list, TreeNode root) {
if (root == null) {
return -1;
}
int leftLevel = findLeavesHelper(list, root.left);
int rightLevel = findLeavesHelper(list, root.right);
int level = Math.max(leftLevel, rightLevel) + 1;
if (list.size() == level) {
list.add(new ArrayList<>());
}
list.get(level).add(root.val);
root.left = root.right = null;
return level;
}
用conditional overridding来处理level list not initialized的情况, 这个想法其实是不错的, 就跟你要update map entry的时候的思路一样, 那个时候, depending on whether the key is already in the map, 也是可以用overriding来完成一个逻辑;
另外discussion上居然还有人贴暴力解:
public class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> leavesList = new ArrayList< List<Integer>>();
List<Integer> leaves = new ArrayList<Integer>();
while(root != null) {
if(isLeave(root, leaves)) root = null;
leavesList.add(leaves);
leaves = new ArrayList<Integer>();
}
return leavesList;
}
public boolean isLeave(TreeNode node, List<Integer> leaves) {
if (node.left == null && node.right == null) {
leaves.add(node.val);
return true;
}
if (node.left != null) {
if(isLeave(node.left, leaves)) node.left = null;
}
if (node.right != null) {
if(isLeave(node.right, leaves)) node.right = null;
}
return false;
}
}
这是另外一个:
public class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
while (root != null) {
List<Integer> temp = new ArrayList<Integer>();
root = removeLeaves(root, temp);
res.add(temp);
}
return res;
}
private TreeNode removeLeaves(TreeNode root, List<Integer> temp) {
if (root == null) return null;
if (root.left == null && root.right == null) {
temp.add(root.val);
return null;
}
root.left = removeLeaves(root.left, temp);
root.right = removeLeaves(root.right, temp);
return root;
}
}
没时间懒得看了, 以后再说了; 其实真的非要modify input的话我感觉也挺没有意义的, 你全都摘完了之后, 不就肯定是空的么, 有什么好modify step by step的;
这个题目的discussion看完真的是感觉菜比其实也挺多的;
这个题目的最优解相对来说并不是特别难想; 不过想想我这个话也不对, 有些问题我自己也菜比过, 最后写出来的解法比最简单的解法要复杂的多;
这个是一个妹子分享的关于topological sort的做法:
We delete nodes layer by layer: for each round,we delete the nodes whose outdegree=0, and update their parent's outdegree. It's very similar similar with what we did in Topological Sort(in TopoSort,each round we delete those whose indegree=1 and iterate).
Use two HashMap, one for recording the outdegree of each TreeNode, and one for recording the parent of each TreeNode; first traverse the tree and load the maps, and then put those whose outdegree=0 into a Deque and iterate until running out of nodes.
public class Solution{
public List<List<Integer>> findLeaves(TreeNode root){
List<List<Integer>> res=new ArrayList<>();
//record outdegree of every node
HashMap<TreeNode,Integer> outdegree=new LinkedHashMap<TreeNode,Integer>();
//record parent of every node
HashMap<TreeNode,TreeNode> parent=new HashMap<TreeNode,TreeNode>();
loadMap(root,outdegree,parent);
Deque<TreeNode> q=new LinkedList<TreeNode>();
for(TreeNode node:outdegree.keySet()){
if(outdegree.get(node)==0){
q.offer(node);
}
}
while(!q.isEmpty()){
int size=q.size();
List<Integer> tmp=new ArrayList<Integer>();
for(int i=0;i<size;i++){
TreeNode t=q.poll();
tmp.add(t.val);
if(t!=root){
outdegree.put(parent.get(t),outdegree.get(parent.get(t))-1);
if(outdegree.get(parent.get(t))==0){
q.offer(parent.get(t));
}
}
}
res.add(tmp);
}
return res;
}
public void loadMap(TreeNode root,HashMap<TreeNode,Integer> outdegree,HashMap<TreeNode,TreeNode> parent){
if(root==null){
return;
}
if(root.left==null&&root.right==null){
outdegree.put(root,0);
return;
}
int degree=0;
if(root.left!=null){
degree++;
parent.put(root.left,root);
}
if(root.right!=null){
degree++;
parent.put(root.right,root);
}
outdegree.put(root,degree);
loadMap(root.left,outdegree,parent);
loadMap(root.right,outdegree,parent);
}
}
看起来有点复杂, 暂时不看了, 反正后面还是有时间去看. 先记录在这里, 然后在G4G上面看过文章之后什么时候有时间再来看;
Problem 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:
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:
1Now removing the leaf [1] would result in the empty tree:
[]Returns [4, 5, 3], [2], [1].
Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.
Difficulty:Medium
Total Accepted:16.8K
Total Submissions:28.4K
Contributor: LeetCode
Companies
linkedin
Related Topics
tree depth-first search