【LeetCode】二叉树最大宽度 Java 题解

作者：Albert

2022-11-04
北京
本文字数：1623 字
阅读完需：约 5 分钟

题目描述

给你一棵二叉树的根节点 root ，返回树的最大宽度。

树的最大宽度是所有层中最大的宽度。

每一层的宽度被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位带符号整数范围内。

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

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

输入：root = [1,3,2,5]输出：2解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/maximum-width-of-binary-tree著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的每日一题是求二叉树所有层的最大宽度。题目给出了宽带的定义。'将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。'也就是说，每层的 null 也需要计数。
求二叉树所有层的最大宽度，我们一般使用 BFS，然后统计每层的宽度，在比较。求每一层的宽度时，因为两端点间的 null 节点也需要计入宽度，因此可以对节点进行编号。一个编号为 idx 的左子节点的编号记为 idx * 2 ，右子节点的编号记为 idx * 2 + 1，计算每层宽度时，用每层节点的最大编号减去最小编号再加 1 即为宽度。然后动态更新即可。
那这样的计算思路是怎么想到的？我们对于一般的完全二叉树，数据存储的时候，使用的是数组结构。假设数组下标从 1 开始，二叉树的根结点存储在位置 1，如果根结点有左孩子，左孩子存储在位置 2 = 2 * 1，如果根结点有右孩子，右孩子存储在位置 3 = 2 * 1 + 1。对于存储在位置 i 的结点，如果它有左孩子，左孩子存储在位置 2 * i，如果它有右孩子，右孩子存储在位置 2 * i + 1。这样就可以转换成 idx 的计算公式。
具体实现代码如下，供参考。

通过代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public int widthOfBinaryTree(TreeNode root) {        Long ans = 0L;        Queue<TreeNode> queue = new LinkedList<>();        Queue<Long> numQueue = new LinkedList<>();
        queue.offer(root);        numQueue.offer(1L);        while (!queue.isEmpty()) {            int size = queue.size();            Long left = Long.MAX_VALUE;            Long right = Long.MIN_VALUE;            for (int i = 0; i < size; i++) {                TreeNode temp = queue.poll();                Long idx = numQueue.poll();                left = Math.min(left, idx);                right = Math.max(right, idx);
                if (temp.left != null) {                    queue.offer(temp.left);                    numQueue.offer(idx * 2);                }                if (temp.right != null) {                    queue.offer(temp.right);                    numQueue.offer(idx * 2 + 1);                }            }            ans = Math.max(ans, right - left + 1);        }        return  ans.intValue();    }}