二叉树的最大宽度

[编程题]二叉树的最大宽度

热度指数：2340 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树，请你求出此二叉树的最大宽度。

本题中树第 i 层的宽度定义为：第 i 层最左边的节点到最右边之间的距离，中间空节点也计入距离。

例如：

本树中第 1 层只有一个节点，故第 1 层宽度是 1 ，第二层最左侧到最右侧的距离是 2 ，所以宽度是 2 ，第三层最左侧 4 到最右侧 5 距离是 4 ，故宽度是 4，此树最大宽度是 4。

示例1

输入

{1,2,3,4,#,4,5}

输出

说明

如题面图

示例2

输入

{1}

输出

示例3

输入

{1,2,3,4,#,4,5,6,#,1}

输出

说明

倒数第二层的宽度为5

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

fatzard

用C写到了排行第五的代码

层次遍历就行了，将节点val值改为他在完全二叉树中第几的位置，用两个指针pre和front记录最左边和最右边，然后每到新的一层两数相减即可，值得注意的是，最后一层要特殊处理一下

#include <stdio.h>
int max(int a,int b)
{
    if(a>b)return a;
    else return b;
}
int widthOfBinaryTree(struct TreeNode* root ) {
    if(root==NULL)return 0;
    struct TreeNode** que=(struct TreeNode**)malloc(sizeof(struct TreeNode*)*100);
    int l=-1,r=-1;
    int ans=1;
    que[++r]=root;
    root->val=1;
    struct TreeNode* front=root;
    struct TreeNode* pre=root;
    struct TreeNode* lateleft=NULL;
    while(l<r)
    {
        root=que[++l];
        if(root==front)
        {
            if(l!=0)pre=que[l-1];
            ans=max(ans,pre->val-front->val+1);
            front=NULL;
            lateleft=root;
        }
        if(root->left)
        {
            root->left->val=root->val*2;
            if(front==NULL)front=root->left;
            que[++r]=root->left;
        }
        if(root->right)
        {
            root->right->val=root->val*2+1;
            if(front==NULL)front=root->right;
            que[++r]=root->right;
        }
    }
    pre=que[r];
    ans=max(ans,pre->val-lateleft->val+1);
    return ans;
}

发表于 2023-10-14 16:21:33 回复(0)