算法练习-二叉树的层序遍历(思路+流程图+代码)

难度参考

        难度:中等

        分类:二叉树

        难度与分类由我所参与的培训课程提供,但需要注意的是,难度与分类仅供参考。且所在课程未提供测试平台,故实现代码主要为自行测试的那种,以下内容均为个人笔记,旨在督促自己认真学习。

题目

        给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。
        示例1:
        输入:root=[3,9,20,null,null,15,7]
        输出:[3],[9,20],[15,7]
        提示:
        树中节点数目在范围[0,20]内
        -100<=Node.Val<=1000

思路

        对于这个问题,我们可以使用广度优先搜索(BFS)算法来进行二叉树的层序遍历。BFS 通常使用队列来实现,通过不断出队和入队的方式,将每一层的节点依次遍历。

  1. 首先,我们需要定义一个队列(queue)来存储待遍历的节点。初始时,将根节点(root)入队。
  2. 然后,进入循环,直到队列为空。在每一次循环中,分别执行以下步骤:
    • 从队列中取出当前节点,并将当前节点的值存入结果数组中(该层的结果数组)。
    • 如果当前节点的左子节点不为空,将左子节点入队。
    • 如果当前节点的右子节点不为空,将右子节点入队。
  3. 循环结束后,我们就能得到一个每层节点值的层序遍历结果数组。

        最后,根据题目的要求,返回层序遍历的结果数组。

示例

        假设我们有以下的二叉树:

     3
    / \
   9  20
     /  \
    15   7

        我们可以按照层序遍历的顺序逐层访问节点。根据题目要求,层序遍历的结果数组应该是 [3], [9, 20], [15, 7]

  1. 首先,将根节点 3 入队。
         3                     --------------------
        / \                      3
       9  20                   --------------------        
         /  \
        15   7                 result = {}
    
  2. 开始循环,第一层级只有根节点 3,所以当前队列中只有根节点 3。将根节点 3 出队,并将其值 3 放入当前层级结果数组中。然后,检查节点 3 的左右子节点,发现都不为空,将根节点的左子节点 9 入队,右子节点 20 入队。
         3                     --------------------
        / \                      9, 20
       9  20                   --------------------        
         /  \
        15   7                 result = {3}
    
  3. 进入下一层级循环。此时,队列中有两个节点,分别是节点 9 和节点 20。将节点 9 出队,并将其值 9 放入当前层级结果数组中。然后,检查节点 9 的左右子节点,发现都为空,所以不需要入队。接着,将节点 20 出队,并将其值 20 放入当前层级结果数组中。然后,将节点 20 的左子节点 15 入队,右子节点 7 入队。
         3                     --------------------
        / \                      15, 7
       9  20                   --------------------        
         /  \
        15   7                 result = {3, 9, 20}
    
  4. 再次进入下一层级循环。此时,队列中有两个节点,分别是节点 15 和节点 7。将节点 15 出队,并将其值 15 放入当前层级结果数组中。然后,检查节点 15 的左右子节点,发现都为空,所以不需要入队。接着,将节点 7 出队,并将其值 7 放入当前层级结果数组中。然后,检查节点 7 的左右子节点,发现都为空,所以不需要入队。
         3                     --------------------
        / \                      
       9  20                   --------------------        
         /  \
        15   7                 result = {3, 9, 20, 15, 7}
    
  5. 循环结束,得到层序遍历的结果数组 [3], [9, 20], [15, 7]

梳理

        对于二叉树的层序遍历,使用队列是因为队列的先进先出(FIFO)特性能够确保每一层的节点按照从左到右的顺序被访问

        具体来说,层序遍历的思路是从根节点开始,依次将节点的左子节点和右子节点加入到队列中,然后从队列中取出节点进行访问。这样做可以保证每一层的节点按照从左到右的顺序进行访问,因为队列中先入队的节点会先出队。

        通过使用队列,保证了层序遍历的节点访问顺序正确,能够按照层级逐步扩展,并且能够将每一层的节点按照顺序存储到结果数组中。

        具体流程中,我们通过循环不断从队列中取出节点,并将其值存入结果数组中。然后,检查当前节点的左右子节点,如果存在则将其加入到队列中,以便后续的访问。

        总结来说,队列在层序遍历中起到了承载节点的作用,能够确保每一层的节点按照顺序被访问。通过队列的先进先出特性,我们能够按照层级逐步扩展,从而得到二叉树的层序遍历结果。

代码

#include <iostream> // 包含输入输出流库
#include <queue> // 包含队列库
#include <vector> // 包含向量库

using namespace std; // 使用标准命名空间

// 定义二叉树的节点
struct TreeNode {
    int val; // 节点值
    TreeNode* left; // 左子节点指针
    TreeNode* right; // 右子节点指针
    
    // 构造函数
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 层序遍历函数
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result; // 存放最终层序遍历结果的向量
    
    // 如果根节点为空,直接返回空结果
    if (root == nullptr) {
        return result;
    }
    
    // 创建队列,并将根节点入队
    queue<TreeNode*> q;
    q.push(root);
    
    // 循环遍历队列,直到队列为空
    while (!q.empty()) {
        // 获取当前层的节点数量
        int size = q.size();
        vector<int> levelNodes; // 存放当前层节点值的向量
        
        // 遍历当前层的节点
        for (int i = 0; i < size; i++) {
            // 弹出队列首节点,并将其值存入结果数组中
            TreeNode* node = q.front();
            q.pop();
            levelNodes.push_back(node->val);
            
            // 将当前节点的左子节点和右子节点入队
            if (node->left) {
                q.push(node->left);
            }
            
            if (node->right) {
                q.push(node->right);
            }
        }
        
        // 将当前层的节点值数组存入结果数组中
        result.push_back(levelNodes);
    }
    
    // 返回结果数组
    return result;
}

int main() {
    // 创建示例树 [3, 9, 20, null, null, 15, 7]
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    // 执行层序遍历
    vector<vector<int>> result = levelOrder(root);

    // 输出结果
    for (const auto& level : result) { // 遍历每一层
        cout << "["; // 给输出结果添加左括号
        for (const auto& val : level) { // 遍历当前层的节点值
            cout << val << ","; // 输出节点值和逗号
        }
        cout << "]"; // 给输出结果添加右括号
    }
    
    return 0;
}

        时间复杂度:O(n)
        空间复杂度:O(n)

  1. pop 是队列的操作,用于移除队列中的队头元素(第一个元素)。
  2. push 是队列的操作,用于将元素添加到队尾。
  3. push_back 是向量的操作,用于将元素添加到向量的末尾。

        在代码中,首先创建一个空的队列 q,然后使用 q.push(root) 将根节点 root 添加到队列中。接下来,通过循环遍历队列,每次从队列中取出一个节点,并将其值添加到 levelNodes 向量中。
同时,如果节点有左子节点或右子节点,通过 q.push 将它们添加到队列的尾部,以便在后续循环中处理它们。
        最后,将 levelNodes 添加到 result 向量中,表示当前层的节点值。
整个过程将重复直到队列为空。最后返回 result 向量,即为二叉树的层序遍历结果。

        在主函数中,示例了如何使用 levelOrder 函数来执行对创建的二叉树进行层序遍历,并将结果输出到屏幕上。

打卡

转载请说明出处内容投诉
CSS教程_站长资源网 » 算法练习-二叉树的层序遍历(思路+流程图+代码)

发表评论

欢迎 访客 发表评论

一个令你着迷的主题!

查看演示 官网购买