leetocde662. 二叉树最大宽度,面试必刷题,思路清晰,分点解析,附代码详解带你完全弄懂
leetocde662. 二叉树最大宽度
做此题之前可以先做一下二叉树的层序遍历。具体题目如下:
leetcode102 | 二叉树的层序遍历 |
---|
我也写过题解,可以先看看学习一下,如果会做层序遍历了,那么这题相对来说会简单很多。
具体题目
给你一棵二叉树的根节点 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) 。
1.预分析
核心思想还是使用广度优先搜索(BFS)来遍历二叉树的每一层。
但这题不一样的是,它必须多保存一个数据,即二叉树的节点位置。
节点位置编号的重要性
在二叉树的层序遍历中,通常只需要访问每个节点一次。然而,为了计算宽度,即树的层间最大节点数,我们还需要知道每个节点在层中的位置。这就需要为每个节点分配一个唯一的位置编号,以反映其在层中的相对位置。
完全二叉树的位置编号策略
在完全二叉树中,每个节点的位置可以通过其在层中的索引来表示。对于任意节点,其左子节点的索引是当前节点索引的2倍,右子节点的索引是当前节点索引的2倍加1。这种索引策略允许我们快速地为子节点分配新的位置编号,而不需要额外的计算。
pair数据结构
由于既要保存二叉树节点,又要保存二叉树的位置,所以我们需要pair数据结构同时保存两个数据。
pair 是一个在 C++ 标准库中定义的模板类,用于存储两个元素的组合。它通常用于需要同时存储两个相关数据的场景。
访问元素:pair 提供了 first 和 second 两个成员变量,分别用于存储和访问第一个和第二个元素。例如,pair<int, double> p(3, 4.5); 创建了一个 pair 对象 p,其中 p.first 是整数3,p.second 是浮点数4.5。
2.算法思路分析
输入检查:首先检查传入的二叉树根节点 root 是否为 nullptr。如果是,说明二叉树为空,其宽度为0,直接返回。
初始化变量:定义一个 unsigned long long 类型的变量 maxWidth 用于存储遍历过程中计算出的最大宽度。同时,定义一个队列 q,用于存储当前层的节点以及它们的位置编号。队列中的元素是一个 pair,包含一个 TreeNode* 类型的节点指针和一个 unsigned long long 类型的位置编号。
初始化队列:将根节点和其位置编号1作为队列的第一个元素。
BFS遍历:使用 while 循环,只要队列不为空,就继续执行。循环中,首先获取队列中的元素数量 size,这代表了当前层的节点数。然后,通过访问队列的前端和后端,获取当前层的最左边和最右边节点的位置编号 left 和 right。
计算宽度:使用 maxWidth 变量来记录到目前为止遍历到的最大宽度。在每次循环中,更新 maxWidth 为当前层宽度和 maxWidth 中较大值。当前层的宽度通过 (right - left + 1) 计算得出。
节点处理:在循环的内部,使用一个 for 循环来处理当前层的每个节点。对于队列中的每个元素,首先获取节点指针 node 和其位置编号 pos,然后从队列中移除该元素。接着,检查当前节点是否有左子节点和右子节点,如果有,计算它们的位置编号并将其加入队列。左子节点的位置编号是当前节点位置编号的2倍,右子节点的位置编号是当前节点位置编号的2倍加1。
循环结束:当队列为空时,表示已经遍历完所有层的节点,此时 maxWidth 中存储的就是二叉树的最大宽度。
3.算法特点分析
数据结构:算法使用了队列作为主要的数据结构,以实现BFS遍历。队列中的元素是包含节点指针和位置编号的 pair,这使得算法能够在每一层结束时快速确定最左边和最右边的节点。
时间复杂度:算法的时间复杂度为 O(n),其中 n 是二叉树中的节点数。这是因为每个节点恰好被访问一次。
空间复杂度:算法的空间复杂度为 O(w),其中 w 是二叉树的最大宽度。这是因为在任何给定时间,队列中最多会有 w 个节点。
位置编号:算法通过为每个节点分配一个位置编号来简化宽度的计算。这种方法避免了需要维护一个复杂的数据结构来跟踪每层的节点。
4.具体代码如下:
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if(root == nullptr)
return 0;
unsigned long long maxWidth = 0;
queue<pair<TreeNode*,unsigned long long>> q; // 使用队列保存每个节点和它对应的位置编号
q.push(pair{root, 1});
while(!q.empty()){
int size = q.size();
unsigned long long left = q.front().second; // 当前层最左边节点的位置编号
unsigned long long right = q.back().second; // 当前层最右边节点的位置编号
maxWidth = max(maxWidth, (right - left + 1)); // 计算当前层的宽度
for(int i = 0; i < size; i++){
TreeNode* node = q.front().first;
unsigned long long pos = q.front().second;
q.pop();
if(node->left)
q.push(pair{node->left, pos * 2}); // 左子节点的位置编号是当前节点的位置编号乘以2
if(node->right)
q.push(pair{node->right, pos * 2 + 1}); // 右子节点的位置编号是当前节点的位置编号乘以2加1
}
}
return maxWidth;
}
};
原文地址:https://blog.csdn.net/qq_51350957/article/details/140695170
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!