Leetcode刷题100天—662. 二叉树最大宽度(二叉树)—day09

ゝ一纸荒年。 2022-09-10 04:19 172阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210903230453604][]

#### [662. 二叉树最大宽度][662.] ####

难度中等247收藏分享切换为英文接收动态反馈

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与\*\*满二叉树（full binary tree）\*\*结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的`null`节点也计入长度）之间的长度。

**示例 1:**

输入: 
    
               1
             /   \
            3     2
           / \     \  
          5   3     9 
    
    输出: 4
    解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

**示例 2:**

输入: 
    
              1
             /  
            3    
           / \       
          5   3     
    
    输出: 2
    解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

**示例 3:**

输入: 
    
              1
             / \
            3   2 
           /        
          5      
    
    输出: 2
    解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

**示例 4:**

输入: 
    
              1
             / \
            3   2
           /     \  
          5       9 
         /         \
        6           7
    输出: 8
    解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

**注意:** 答案在32位有符号整数的表示范围内。

package 二叉树;
    
    import java.util.LinkedList;
    import java.util.Queue;
    /* * 8 * https://leetcode-cn.com/problems/maximum-width-of-binary-tree/submissions/ */
    public class _662_二叉树最大宽度 { 
    // 宽度优先搜索[Accepted]
    	public int widthOfBinaryTree(TreeNode root) { 
    		if (root==null) { 
    			return 0;
    		}
    		//设置队列
    		Queue<AnnotatedNode> queue=new LinkedList<>();
    // 将头节点入队
    		queue.offer(new AnnotatedNode(root, 0, 0));
    // 设置值，left作用是判断最左边节点的位置
    		int ans=0,curDepth=0,left=0;
    // 如果队列为空就终止循环
    		while(!queue.isEmpty()) { 
    // 出队
    			AnnotatedNode c=queue.poll();
    // 如果节点不为空就判断
    			if (c.node!=null) { 
    // 该节点的左右节点入队,深度加1,位置由原来的位置乘2
    				queue.offer(new AnnotatedNode(c.node.left, c.depth+1, c.pos*2));
    				queue.offer(new AnnotatedNode(c.node.right, c.depth+1, c.pos*2));
    // 如果深度不一样,调整最左边节点的位置
    				if (curDepth!=c.depth) { //每层第一个（最左）出栈以后会更新最左标志
    					curDepth=c.depth;
    					left=c.pos;
    				}
    // 通过最右边减去最左边判断宽度
    				ans=Math.max(ans, c.pos-left+1);//每次出栈一个节点都会计算一次
    			}
    			
    			
    		}
    		return ans;
        }
    // 设置参数
    	class AnnotatedNode{ //用于包装一下树的节点来记录每个节点的数学位置和层位置
    		TreeNode node;
    // 这里的depth是树的深度，pos是位置
    		int depth,pos;
    		AnnotatedNode(TreeNode a,int b,int c){ 
    			node=a;
    			depth=b;
    			pos=c;
    		}
    	}
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210903230453604]: /images/20220829/8466c54e765d4e40a825154a89690568.png
[662.]: https://leetcode-cn.com/problems/maximum-width-of-binary-tree/