当前位置:   article > 正文

leetocde662. 二叉树最大宽度,面试必刷题,思路清晰,分点解析,附代码详解带你完全弄懂

leetocde662. 二叉树最大宽度,面试必刷题,思路清晰,分点解析,附代码详解带你完全弄懂

leetocde662. 二叉树最大宽度

做此题之前可以先做一下二叉树的层序遍历。具体题目如下:

我也写过题解,可以先看看学习一下,如果会做层序遍历了,那么这题相对来说会简单很多。

具体题目

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/890759
推荐阅读
相关标签
  

闽ICP备14008679号