二叉树最大宽度

简介: 二叉树最大宽度

Width first traversal

数据

使用变量curLevel 记录当前遍历层数 ;curLevelnode 记录当前层的节点个数

哈希表Level记录节点与它所在层数的对应关系

队列NodeSeq实现层序遍历


思路

将根节点和它所在第一层入哈希表Level

根节点入队列NodeSeq,进行层序遍历

每次pop节点Front,比较Front所在层数与curLevel


实现

void WidthMax(Node* root)
{
    if(root != nullptr)
    {
        queue<Node*> NodeSeq;
        int curLevel = 1;
        int curLevelnode = 0;
        unordered_map<Node*,int> Level;
        int width = -1;
        Level[root] = 1;
        NodeSeq.push(root);
        while(!NodeSeq.empty())
        {
            Node* Front = NodeSeq.front();
            NodeSeq.pop();
            if(Level[Front] == curLevel)
            {
                curLevelnode++;
            }
            else
            {
                width = max(width,curLevelnode);
                curLevel++;
                curLevelnode = 1;
            }
            if(Front->left) 
            {
                NodeSeq.push(Front->left);
                Level[Front->left] = curLevel + 1;
            }
            if(Front->right)
            {
                NodeSeq.push(Front->right);
                Level[Front->right] = curLevel + 1;
            }
        }
        cout << width << endl;
    }
}


总结

使用Hashmap记录当前节点所在层数,根据层序遍历的顺序了解节点所在层的变化

目录
相关文章
|
7月前
|
C++
翻转二叉树(C++)
翻转二叉树(C++)
33 0
【Leetcode -404.左子叶之和 -543.二叉树的直径】
【Leetcode -404.左子叶之和 -543.二叉树的直径】
60 0
|
人工智能
1215 数组的宽度 单调栈
1215 数组的宽度 单调栈
48 0
|
Java
求一颗二叉树的宽度
求一颗二叉树的宽度
100 0
求一颗二叉树的宽度
|
存储 C++
求二叉树的高度(C++递归实现)
求二叉树的高度(C++递归实现)
130 0
二叉树——226. 翻转二叉树
本专栏按照数组—链表—哈希—字符串—栈与队列—二叉树—回溯—贪心—动态规划—单调栈的顺序刷题,采用代码随想录所给的刷题顺序,一个正确的刷题顺序对算法学习是非常重要的,希望对大家有帮助
二叉树——226. 翻转二叉树
AcWing 745. 数组的右上半部分
AcWing 745. 数组的右上半部分
52 0
AcWing 745. 数组的右上半部分