每日一题：Leetcode-662 二叉树最大宽度

力扣题目

解题思路

java代码

力扣题目：

给你一棵二叉树的根节点 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) 。

解题思路：

算法原理：
通过层次遍历二叉树，同时利用一个队列记录节点，另一个队列记录节点对应的索引。在每一层计算起始索引和结束索引的差值来得到当前层的宽度，并更新最大宽度。

思路：
在遍历过程中，根据节点的左右子节点更新队列，左子节点索引为当前节点索引的 2 倍，右子节点索引为当前节点索引的 2 倍加 1。不断计算每一层的宽度并与最大宽度比较更新。

代码分析：

• widthOfBinaryTree 方法中，先初始化节点队列和索引队列，将根节点及其索引 1 加入队列。
• 进入循环，获取当前层节点数量。
• 遍历当前层节点，获取节点和对应索引，记录起始和结束索引。
• 根据节点的左右子节点更新队列和索引队列。
• 计算当前层宽度并更新最大宽度。

时间复杂度：O（n），因为需要遍历所有节点。
空间复杂度：O(n)，主要是两个队列的空间占用。

java代码：

package org.example.mouth8;

import java.util.LinkedList;
import java.util.Queue;

public class Leetcode662 {

    public static int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> indexQueue = new LinkedList<>();

        nodeQueue.offer(root);
        indexQueue.offer(1);

        int maxWidth = 0;

        while (!nodeQueue.isEmpty()) {
            int size = nodeQueue.size();
            int startIndex = 0;
            int endIndex = 0;

            for (int i = 0; i < size; i++) {
                TreeNode node = nodeQueue.poll();
                int index = indexQueue.poll();

                if (i == 0) {
                    startIndex = index;
                }
                if (i == size - 1) {
                    endIndex = index;
                }

                if (node.left!= null) {
                    nodeQueue.offer(node.left);
                    indexQueue.offer(2 * index);
                }
                if (node.right!= null) {
                    nodeQueue.offer(node.right);
                    indexQueue.offer(2 * index + 1);
                }
            }

            maxWidth = Math.max(maxWidth, endIndex - startIndex + 1);
        }

        return maxWidth;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        System.out.println(widthOfBinaryTree(root));
    }
}

更多详细内容同步到公众号，感谢大家的支持！

每天都会给刷算法的小伙伴推送明日一题，并且没有任何收费项