寸_铁

这个屌丝很懒，什么也没留下！

热门标签

代码随想录DAY13 - 二叉树 - 08/12 (层序遍历)

作者：寸_铁 | 2024-08-18 06:47:53

踩

理论回顾

二叉树的种类

满二叉树和完全二叉树

种类	满二叉树	完全二叉树
定义	只有度为0的结点和度为2的结点，并且度为0的结点在同一层上。	在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最底层的节点都集中在该层最左边的若干位置。（可以理解为要按从上到下、从左到右的顺序填充结点）
深度和结点的关系	设深度为k，满二叉树的节点个数 = 2^k-1（等比数列求和）	若最底层为第 h 层（h从1开始），则该层包含 1 ~ 2^(h-1) 个节点。

二叉搜索树和平衡二叉搜索树

二叉搜索树：每个结点带有权值，权值大小关系满足：左子树 < 父节点 < 右子树

平衡二叉搜索树：是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

注意：C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树

二叉树的存储方式

链式存储

二叉树的链式存储节点结构包括数据域、左孩子指针、右孩子指针，链式存储通过指针把分布在内存各地址的节点串联一起。

链式存储中二叉树结点的定义：


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    // 构造函数
    TreeNode(int x): val(x),left(nullptr),right(nullptr){}
};

顺序存储

用数组存储二叉树的各个结点，如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树的遍历方式

二叉树主要有两种遍历方式：

深度优先遍历：先往深走，遇到叶子节点再往回走。
- 前序遍历（递归法，迭代法）（中左右）
- 中序遍历（递归法，迭代法）（左中右）
- 后序遍历（递归法，迭代法）（左右中）
  
  注意：前中后序指的是中间结点的遍历顺序，前序即中间结点最前，中序即中间结点居中，后序即中间节点最后。
广度优先遍历：一层一层的去遍历。
- 层序遍历（迭代法）

其中，深度优先遍历递归法主要应用到栈，广度优先遍历一般用队列实现。

题单

二叉树的遍历方式：前序遍历、中序遍历、后序遍历、层序遍历

二叉树的属性：对称二叉树、二叉树的最大深度、二叉树的最小深度、完全二叉树的节点个数、平衡二叉树、二叉树的所有路径、左叶子之和、找树左下角的值、路径总和

二叉树的修改与构造：翻转二叉树、从中序和后续遍历序列构造二叉树、最大二叉树、合并二叉树

二叉搜索树：二叉搜索树的搜索、验证二叉搜索树的最小绝对差、二叉搜索树中的众数、把二叉搜索树转换为累加树

二叉树公共祖先问题：二叉树的最近公共祖先、二叉搜索树的最近公共祖先

二叉搜索树的修改和构造：二叉搜索树的插入操作、删除二叉搜索树中的节点、修剪二叉搜索树、将有序数组转换为二叉搜索树

层序遍历

题干

题目：给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。注意，不一定是完全二叉树。

链接：. - 力扣（LeetCode）

思路

这道题目是要按层存储节点值，即同一层的节点值在同一个数组中，并且再用一个数组存储不同的层，也就是返回二维数组。

首先用一个指针 cur 遍历二叉树的节点。但关键是如何实现从上到下、从左到右的遍历顺序？

我们用指针 cur 遍历时，不仅可以访问当前节点的值，同时也知道是否有左右孩子。当 cur 遍历完一层的节点，其实也就知道了下一层有多少个节点，数出来有多少个孩子即可。因此可以用一个队列提前存储下一层的节点，利用队列的先进先出特性，我们只需要让左孩子比右孩子先入队，就可以保证是从左到右遍历，同时遍历完一层节点以后，队列的长度就是下一层的节点个数。

代码


class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        // 如果根节点为空，直接返回空数组，如果不判空，后续会报错
        if (root == nullptr){
            return {};
        }
        
        TreeNode* cur = root; // 遍历每一个节点
        int count = 1; // 记录每一层的节点个数，第一层只有根节点，节点个数为 1
 
        queue<TreeNode*> tmpNode; // 存储每一层的节点
        tmpNode.push(root); // 初始只存储第一层的根节点
 
        vector<vector<int>> result; // 存储层序遍历的结果
        vector<int> nodesPerLayer; // 存储同一层的节点值
        
		// 当队列为空说明已经遍历完所有节点
        while (!tmpNode.empty()){
            // 遍历当前层的节点
            while (count--){
                cur = tmpNode.front(); // 弹出队头
                nodesPerLayer.push_back(cur->val); // 存储节点值
                tmpNode.pop(); // 弹出节点
                // 将左右孩子节点入队
                if (cur->left != nullptr){
                    tmpNode.push(cur->left);
                }
                if (cur->right != nullptr){
                    tmpNode.push(cur->right);
                }
            }
            count = tmpNode.size(); // 队列长度就是下一层的节点个数
            result.push_back(nodesPerLayer); // 将当前层的节点值存入数组
            nodesPerLayer.clear();// 清空当前层节点值数组，为存储下一层准备
        }
        return result;
    }
};

层序遍历的拓展题目

二叉树的层次遍历Ⅱ

题干

二叉树的层次遍历Ⅱ

题目：给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路

按照上一道题的思路，先存储自顶向下的层序遍历数组，若要变成自底向上，只需将数组翻转即可。

代码


class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        // 如果根节点为空，直接返回空数组，如果不判空，后续会报错
        if (root == nullptr){
            return {};
        }
 
        TreeNode* cur = root;
        int count = 1; // 记录每一层的节点个数，第一层只有根节点，节点个数为 1
 
        queue<TreeNode*> tmpNode; // 存储每一层的节点
        tmpNode.push(root); // 初始只存储根节点
 
        vector<vector<int>> result; // 存储层序遍历的结果
        vector<int> nodesPerLayer; // 存储一层的节点值
 
        while (!tmpNode.empty()){
            while (count--){
                cur = tmpNode.front(); // 弹出队头
                nodesPerLayer.push_back(cur->val); // 存储节点值
                tmpNode.pop(); // 弹出节点
                if (cur->left != nullptr){
                    tmpNode.push(cur->left);
                }
                if (cur->right != nullptr){
                    tmpNode.push(cur->right);
                }
            }
            count = tmpNode.size(); // 队列长度就是下一层的节点个数
            result.push_back(nodesPerLayer); // 当前节点值已经存储在数组中
            nodesPerLayer.clear();// 清空当前层节点值数组，为存储下一层准备
        }
        
        // 多了一步翻转数组!!!!
        reverse(result.begin(),result.end());
        
        return result;
    }
};

二叉树的右视图

题干

题目：给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

链接：. - 力扣（LeetCode）

思路

在层序遍历的基础上，每次只需要存储一层最右边的节点。

代码


class Solution {
 public:
     vector<int> rightSideView(TreeNode* root) {
         // 如果根节点为空，直接返回空数组，如果不判空，后续会报错
         if (root == nullptr){
             return {};
         }
 
         TreeNode* cur = root;
         int count = 1; // 记录每一层的节点个数，第一层只有根节点，节点个数为 1
 
         queue<TreeNode*> tmpNode; // 存储每一层的节点
         tmpNode.push(root); // 初始只存储根节点
 
         vector<int> result; // 存储每一层最右边的节点值！！！修改
 
         while (!tmpNode.empty()){
             while (count--){
                 cur = tmpNode.front(); // 弹出队头
                 if (count == 0){
                     // 存储最后右边节点，即 count = 0 时，修改！！！
                     result.push_back(cur->val);
                 }
                 tmpNode.pop(); // 弹出节点
                 if (cur->left != nullptr) tmpNode.push(cur->left);
                 if (cur->right != nullptr) tmpNode.push(cur->right);
             }
             count = tmpNode.size(); // 队列长度就是下一层的节点个数
         }
         return result;
     }
 };

二叉树的层平均值

题干

题目：给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10^(-5) 以内的答案可以被接受。

链接：. - 力扣（LeetCode）

思路

在层序遍历二叉树时，计算出每一层节点的总和，再除以当前层的节点数就可求平均值。

代码


class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if (root == nullptr){
            return {};
        }
 
        TreeNode* cur = root;
        int count = 1; // 记录每一层的节点个数，第一层只有根节点，节点个数为 1
 
        queue<TreeNode*> tmpNode; // 存储每一层的节点
        tmpNode.push(root); // 初始只存储根节点
 
        vector<double> result; // 存储每一层节点的平均值，修改！！！
 
        while (!tmpNode.empty()){
            // sum 要用 double 存储，如果用 int 会溢出报错！！！
            double sum = 0; // 存储一层的节点值总和
            
            for (int i = 0; i < count; ++i) {
                cur = tmpNode.front(); // 弹出队头
                sum += cur->val; // 将每个节点值加起来，修改！！
                tmpNode.pop(); // 弹出节点
                if (cur->left != nullptr) tmpNode.push(cur->left);
                if (cur->right != nullptr) tmpNode.push(cur->right);
            }
            double avg = sum/count; // 求平均值
            result.push_back(avg); // 存储平均值
            count = tmpNode.size(); // 队列长度就是下一层的节点个数
        }
        return result;
    }
};

报错记录

runtime error: signed integer overflow

不能用 int 表示每一层的节点值总和，因为一个节点值最大可能是 2^31-1，当多个这么大的节点值相加，总和肯定超过 int 的最大表示范围了。因此每一次层的节点值总和 sum 要用 double 型表示。

N叉树的层序遍历

题干

题目：给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

链接：. - 力扣（LeetCode）

思路

和二叉树的层序遍历思路相同，只不过二叉树在遍历每个节点时，只需要将左右孩子入队；而 N叉树是需要将 N 个孩子节点入队。同时还需要注意题目中对 N 叉树的结点是如何定义的。

代码


/*
// N 叉树的结点定义
class Node {
public:
    int val;
    vector<Node*> children; // 孩子节点用一个数组存储
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
 
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        if (root == nullptr){
            return {};
        }
 
        Node* cur = root; // 注意数据类型为 Node！！！
        int count = 1;
 
        queue<Node*> tmpNode; // 存储每一层的节点
        tmpNode.push(root); // 初始只存储根节点
 
        vector<vector<int>> result; // 存储层序遍历的结果
        vector<int> nodesPerLayer; // 存储一层的节点值
 
        while (!tmpNode.empty()){
            while (count--){
                cur = tmpNode.front(); // 弹出队头
                nodesPerLayer.push_back(cur->val); // 存储节点值
                tmpNode.pop();
                // N 叉树是将 0~N 个孩子结点入队，修改处！！！
                if (cur->children.size() > 0){
                    for (Node* child : cur->children) {
                        tmpNode.push(child);
                    }
                }
            }
            count = tmpNode.size(); // 队列长度就是下一层的节点个数
            result.push_back(nodesPerLayer); // 当前节点值已经存储在数组中
            nodesPerLayer.clear();// 清空当前层节点值数组，为存储下一层准备
        }
        return result;
    }
};

在每个树行中找最大值

题干

题目：给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

链接：. - 力扣（LeetCode）

思路

同样是层序遍历，在遍历每一层的同时记录最大值即可。

代码


class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        // 如果根节点为空，直接返回空数组，如果不判空，后续会报错
        if (root == nullptr){
            return {};
        }
 
        TreeNode* cur = root;
        int count = 1; // 记录每一层的节点个数，第一层只有根节点，节点个数为 1
 
        queue<TreeNode*> tmpNode; // 存储每一层的节点
        tmpNode.push(root); // 初始只存储根节点
 
        vector<int> result; // 存储每一层的最大值，修改处！！！
 
        while (!tmpNode.empty()){
            int max = tmpNode.front()->val; // 记录每一层的最大值，初始为每层第一个结点的数值
            while (count--){
                cur = tmpNode.front(); 
                if (cur->val > max){ // 修改处！！！
                    max = cur->val;
                }
                tmpNode.pop();
                if (cur->left != nullptr){
                    tmpNode.push(cur->left);
                }
                if (cur->right != nullptr){
                    tmpNode.push(cur->right);
                }
            }
            count = tmpNode.size(); // 队列长度就是下一层的节点个数
            result.push_back(max); // 将每一层的最大值存入数组中，修改处！！
        }
        return result;
    }
};

填充每个结点的下一个右侧指针

题干

题目：给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：


struct Node {
  int val;
  Node *left; // 左孩子
  Node *right; // 右孩子
  Node *next; // 同一层中的右侧结点（右兄弟）
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

链接：. - 力扣（LeetCode）

思路

同样是层序遍历，在遍历当前结点时，next 指向的右边结点其实就是队列中的队头元素。

代码


/*
// 完美二叉树的结点定义
class Node {
public:
    int val;
    Node* left; // 左孩子
    Node* right; // 右孩子
    Node* next; // 右侧结点
    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
 
class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr){
            return root;
        }
        Node* cur = root;
        int count = 1; // 记录每一层的节点个数，第一层只有根节点，节点个数为 1
 
        queue<Node*> tmpNode; // 存储每一层的节点
        tmpNode.push(root); // 初始只存储根节点
 
        while (!tmpNode.empty()){
            while (count--){
                cur = tmpNode.front();
                tmpNode.pop();
                // 每一层的最后一个结点不用修改next，默认为null
                if (count > 0){
                    cur->next = tmpNode.front(); // next 指针指向的就是队列中的队头
                }
                if (cur->left != nullptr){
                    tmpNode.push(cur->left);
                }
                if (cur->right != nullptr){
                    tmpNode.push(cur->right);
                }
            }
            count = tmpNode.size(); // 队列长度就是下一层的节点个数
        }
        return root;
    }
};

填充每个节点的下一个右侧节点指针 II

题目：同样也是填充 next 指针。这道题和上一道题目的区别就是二叉树任意，不一定是完全二叉树，也不一定是满二叉树。

链接：. - 力扣（LeetCode）

思路和代码和上一道题一模一样，就不写了。

二叉树的最大深度

题干

题目：给定一个二叉树 root ，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

链接：. - 力扣（LeetCode）

思路

层序遍历二叉树，同时记录遍历了多少层即可。

代码


class Solution {
public:
    int maxDepth(TreeNode* root) {
        // 如果根节点为空，直接返回空数组，如果不判空，后续会报错
        if (root == nullptr){
            return {};
        }
 
        TreeNode* cur = root; // 遍历每一个节点
        int count = 1; // 记录每一层的节点个数，第一层只有根节点，节点个数为 1
 
        queue<TreeNode*> tmpNode; // 存储每一层的节点
        tmpNode.push(root); // 初始只存储第一层的根节点
 
        int result = 0; // 存储层数!!
 
        // 当队列为空说明已经遍历完所有节点
        while (!tmpNode.empty()){
            result++; // 每循环一次说明就多了一层!!!!
            
            while (count--){
                cur = tmpNode.front(); // 弹出队头
                tmpNode.pop(); // 弹出节点
                // 将左右孩子节点入队
                if (cur->left != nullptr){
                    tmpNode.push(cur->left);
                }
                if (cur->right != nullptr){
                    tmpNode.push(cur->right);
                }
            }
            count = tmpNode.size(); // 队列长度就是下一层的节点个数
        }
        return result;
    }
};

二叉树的最小深度

题干

题目：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

链接：. - 力扣（LeetCode）

思路

层序遍历二叉树，只要碰到叶子结点就终止遍历，在哪一层终止就说明最小深度是多少。

代码


class Solution {
public:
    int minDepth(TreeNode* root) {
        // 如果根节点为空，直接返回空数组，如果不判空，后续会报错
        if (root == nullptr){
            return {};
        }
 
        TreeNode* cur = root; // 遍历每一个节点
        int count = 1; // 记录每一层的节点个数，第一层只有根节点，节点个数为 1
 
        queue<TreeNode*> tmpNode; // 存储每一层的节点
        tmpNode.push(root); // 初始只存储第一层的根节点
 
        int result = 0; // 存储层数
 
        // 当队列为空说明已经遍历完所有节点
        while (!tmpNode.empty()){
            result++; // 每循环一次说明就多了一层!!!!
            // 遍历当前层的节点
            while (count--){
                cur = tmpNode.front(); // 弹出队头
                tmpNode.pop(); // 弹出节点
                
                // 判断当前结点是否为叶子结点，若是，则当前结点所在的层数即最小深度!!!!
                if (cur->left == nullptr && cur->right == nullptr){
                    return result;
                }
                
                // 将左右孩子节点入队
                if (cur->left != nullptr){
                    tmpNode.push(cur->left);
                }
                if (cur->right != nullptr){
                    tmpNode.push(cur->right);
                }
            }
            count = tmpNode.size(); // 队列长度就是下一层的节点个数
        }
        return result;
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/996439