力扣662：二叉树的最大宽度

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

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


#define MAX_NUM 20000

int widthOfBinaryTree(struct TreeNode* root) {
    // 如果根节点为空，说明是空树，其宽度为0，直接返回0
    if (root == NULL) {
        return 0;
    }

    // 定义一个数组作为队列，用于存储二叉树节点指针，实现层序遍历等操作
    // 这里假设队列最多能容纳MAX_NUM个节点
    struct TreeNode *q[MAX_NUM];

    // 由于直接在原节点的val值上记录编号可能会超出int范围（对于某些用例），
    // 所以定义一个无符号长整型数组作为辅助数组，用于记录每个节点的编号
    unsigned long long Q[MAX_NUM];

    // 初始化队列头部索引为0
    int front = 0;

    // 初始化队列尾部索引为0
    int rear = 0;

   
    // root->val = 0;

    // 将根节点的编号初始化为1，存储到辅助数组Q中
    Q[rear] = 1;

    // 将根节点入队，作为层序遍历的起始点
    q[rear++] = root;

    // 初始化最大宽度为0，用于在遍历过程中记录遇到的最大宽度值
    int max = 0;

    // 当队列不为空时，进行层序遍历及相关计算
    while (front < rear) {
        // 计算当前层的宽度，这里通过每层最后一个节点的编号减去第一个节点的编号再加1来得到
        // 原先是通过节点的val值来计算，但存在可能超出int范围的问题，现在使用辅助数组Q中的编号来计算
        max = fmax(max, Q[rear - 1] - Q[front] + 1);

        // 本层所有元素出队，同时将子节点入队，并为子节点赋值正确的编号
        int curLevelSize = rear - front;
        for (int i = 0; i < curLevelSize; i++) {
            // 获取当前出队节点的编号
            unsigned long long idx = Q[front];

            // 将当前节点出队
            struct TreeNode *node = q[front++];

            // 如果当前节点的左子节点不为空，为左子节点计算编号并将其入队
            if (node->left!= NULL) {
                // 左子节点的编号为父节点编号乘以2
                Q[rear] = idx * 2;
                q[rear++] = node->left;
            }

            // 如果当前节点的右子节点不为空，为右子节点计算编号并将其入队
            if (node->right!= NULL) {
                // 右子节点的编号为父节点编号乘以2再加1
                Q[rear] = idx * 2 + 1;
                q[rear++] = node->right;
            }
        }
    }

    // 返回计算得到的二叉树的最大宽度
    return max;
}

原文地址：https://blog.csdn.net/m0_56332819/article/details/143777277

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！