LeetCode662：二叉树最大宽度（二叉树非典型最大宽度，BFS层序遍历重编号）

本文主要是介绍LeetCode662：二叉树最大宽度（二叉树非典型最大宽度，BFS层序遍历重编号），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给你一棵二叉树的根节点 root ，返回树的最大宽度。
树的最大宽度是所有层中最大的宽度。
每一层的宽度被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位带符号整数范围内。

示例 1：
在这里插入图片描述

输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9)

在这里插入图片描述
输入：root = [1,3,2,5,null,null,9,6,null,7]
输出：7
解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。

提示：
树中节点的数目范围是 [1, 3000]
-100 <= Node.val <= 100

思路

可以看到本题要求的最大宽度不是寻常的一层节点实际含有的最大节点数，也不是将这棵树构造成满二叉树后，含有空节点在内的最大节点数。

而是某一层最左和最右的非空节点之间的最大长度，其中若含有空节点，空节点也计入长度。

我最先想到的是构造值为负值的空节点进栈，以某一层都为负值的空节点为判断条件判断是否结束遍历，否则会无休止地构造空节点下去。但这样空间时间消耗都很大，无论怎么样都过不了全部样例。随后想到了层序遍历的有序编号实际上可以反映他们的位置信息。

有序编号指的是：
root的编号=N
root.left的编号=2 * N
root.right的编号=2 * N + 1

这时，我们求出某一层最左节点的编号，和最右节点的编号，随后相减便是这层的宽度，然后求最大值即可。

public int widthOfBinaryTree(TreeNode root) {if(root==null) return 0;List<Integer> list = new ArrayList<>();List<List<Integer>> ans = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();queue.add(root);root.val=1;while(!queue.isEmpty()){list = new ArrayList<>();int size = queue.size();for(int i=0;i<size;i++){TreeNode cur = queue.poll();list.add(cur.val);if(cur.left!=null) {queue.add(cur.left);cur.left.val=cur.val*2;}               if(cur.right!=null){queue.add(cur.right);cur.right.val=cur.val*2+1;}       }ans.add(list);}int max=-1;for(List<Integer> li:ans){int last = li.get(li.size()-1);int first = li.get(0);max=Math.max(max,last-first+1);}return max;}