Leetcode 662. 二叉树最大宽度(记录结点逻辑位置)

亦凉 2022-09-15 12:23 144阅读 0赞

## 题目重述 ##

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（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位有符号整数的表示范围内。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/maximum-width-of-binary-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 思路 ##

*  自定义类，记录结点、结点位置、结点所在深度
 *  左结点的位置为父节点root的`pos*2`
 *  右结点的位置为父节点root的`pos*2+1`
 *  记录每一层最左结点所在位置，不断更新最大宽度值，最后返回即可。

## Java实现 ##

class Solution {
        
        private int maxWidth = 0;
        public int widthOfBinaryTree(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }
            // 标记当前所在树的深度
            int currentDepth = 0;
            int leftPos = 0;
            // 树的宽度优先遍历
           Queue<MyNode> q = new LinkedList<>();
           q.add(new MyNode(root,0,0));
           while(!q.isEmpty()){
        
               MyNode a = q.poll();
               // 根据题意，结点是有可能为空的
                if(a.node!=null){
        
                    q.add(new MyNode(a.node.left,a.depth+1,a.pos*2));
                    q.add(new MyNode(a.node.right,a.depth+1,a.pos*2+1));
                    if(currentDepth!=a.depth){
        
                        // 说明换层了
                        currentDepth = a.depth;
                        leftPos = a.pos;
                    }
                    // 更新当前深度
                    maxWidth = Math.max(maxWidth,a.pos-leftPos+1);
                }
           }   
           return maxWidth;
        }
    }
    class MyNode{
        
        public TreeNode node;
        // 标识当前深度
        public int depth;
        // 当前位置
        public int pos;
        public MyNode(TreeNode node,int depth,int pos){
        
            this.node = node;
            this.depth = depth;
            this.pos = pos;
        }
    }