首页 > 编程语言 > 详细

linked list焦点问题,面经里很多,考虑相交不相交,有环无环 + Find Leaves of Binary Tree (Java)

时间:2017-12-02 10:48:29      阅读:279      评论:0      收藏:0      [点我收藏+]

break the loop at the last node which pointed to the entry.

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].

ollowup: 每个node还是有left,right指针,但是结构并非tree,而是graph怎么算, 考虑有/无circular dependency 两种情况;
方法是用hashmap 记录计算过的node level 和 一个Set 记录dependent node
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;
 
    int left = helper(list, root.left);
    int right = helper(list, root.right);
    int curr = 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()<=curr){
        list.add(new ArrayList<Integer>());
    }
 
    list.get(curr).add(root.val);
 
    return curr;
}

  

linked list焦点问题,面经里很多,考虑相交不相交,有环无环 + Find Leaves of Binary Tree (Java)

原文:http://www.cnblogs.com/apanda009/p/7952951.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!