求树的最大宽度和最大深度-蒲公英云

求树的最大宽度和最大深度

以你之姓@ 2022-09-26 02:22 235阅读 0赞

原文地址：http://blog.csdn.net/salahelx/article/details/46727499

二叉树深度：这个可以使用递归，分别求出左子树的深度、右子树的深度，两个深度的较大值+1即可。

private static int getHeight(BiNode head) {  
      if(head==null)            //结束条件  
        return 0;  
      else return 1+Math.max(getHeight(head.left), getHeight(head.right));  
    }

二叉树宽度：使用队列，层次遍历二叉树。在上一层遍历完成后，下一层的所有节点已经放到队列中，此时队列中的元素个数就是下一层的宽度。以此类推，依次遍历下一层即可求出二叉树的最大宽度。

private static int getWidth(BiNode head) {  
        if(head==null)  
            return 0;  
        int max=1;  
        LinkedList<BiNode>ll=new LinkedList<BiNode>();  
        ll.add(head);  
        while(true){  
            int len=ll.size();  
            if(len==0)  
                break;  
            while(len>0){  
                BiNode b=ll.poll();  
                len--;  
                if(b.left!=null)  
                    ll.add(b.left);  
                if(b.right!=null)  
                    ll.add(b.right);  
            }  
            max=Math.max(max, ll.size());  
        }  
        return max;  
    }