662. 二叉树最大宽度

谁践踏了优雅 2022-10-07 15:50 134阅读 0赞

>  
> 
> 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
> 
> 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
> 
>  ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70 1][]

class Solution {
        int max=0;//记录最大值;
        public int widthOfBinaryTree(TreeNode root) {
            /**
            根据二叉树性质: 当前节点的左右子树下标为2*n  2*n +1
            利用bfs即可,然后bfs来确定宽度(当前层最右边的-最左边的 下标即可) ,根据这个来更新最大值
            新建一个类(节点) 
             */
    
            //以下是bfs模板
             Deque<Node> queue=new LinkedList();
             Node node=new Node(root,1);//构建node节点 第0层 下标为0
             queue.add(node);
             while(!queue.isEmpty()){
                 int size=queue.size();
                 int left=queue.getFirst().index;//当前层队首下标
                 int right=queue.getLast().index;//当前层队尾下标
                 max=Math.max(max,right-left+1);      
                                   
                 for(int i=0;i<size;i++){
                     Node curNode=queue.poll();     
                     if(curNode.node.left!=null){
                          queue.add(new Node(curNode.node.left,curNode.index*2));
                     }
                    if(curNode.node.right!=null){
                        queue.add(new Node(curNode.node.right,curNode.index*2+1));    
                    }                       
                 }
             }
             return max;
        }
    }
     class Node{
         public TreeNode node;
         public int index;
    
            Node(TreeNode node,int index){
                this.node=node;
                this.index=index;
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/09e42f84efb24271b7ce606d92da1d1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70 1]: /images/20221005/909a2d0ed7c949809428308deaf83781.png