二叉树最大宽度(节点编号+BFS)

梦想不抛弃苦心追求的人,只要不停止追求,你们会沐浴在梦想的光辉之中。再美好的梦想与目标,再完美的计划和方案,如果不能尽快在行动中落实,最终只能是纸上谈兵,空想一番。只要瞄准了大方向,坚持不懈地做下去,才能够扫除挡在梦想前面的障碍,实现美好的人生蓝图。二叉树最大宽度(节点编号+BFS),希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

二叉树最大宽度(节点编号+BFS)

问题:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

思路:

需对节点编号,每层最后一个节点编号-第一个节点编号+1即为该层宽度
对于满二叉树,若根的编号为x,则其左孩子编号为2x,右孩子编号为2x+1
BFS所使用的队列需保存节点指针及节点的编号

为防止数据超过表示范围,需使用unsigned long long,当队列中只有一个元素,即该层只有一个节点时,可将其编号修正为1,以减少溢出可能

代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    typedef unsigned long long ull;
    int widthOfBinaryTree(TreeNode* root) {
        if( root==NULL )
            return 0;
        queue< pair<TreeNode*,ull> > q;
        TreeNode* p=root;
        q.push( pair<TreeNode*,ull>(p,1) );
        ull ans=1;
        while( !q.empty() )
        {   
            if( q.size()==1 )
                q.front().second=1;
            ull left=q.front().second;
            ull right=left;
            ull size=q.size();
            while( size-- )
            {   
                p=q.front().first;
                right=q.front().second;
                q.pop();
                if( p->left )
                    q.push( pair<TreeNode*,ull>( p->left,right*2 ) );
                if( p->right )
                    q.push( pair<TreeNode*,ull>( p->right,right*2+1 ) );
            }
            if( right-left+1>ans )
                ans=right-left+1;
        }
        return ans;
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/153826.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!