0
0

力扣刷题之二叉树的层序遍历

二叉树的层序遍历

**广度优先搜索 **

我们可以用一种巧妙的方法修改广度优先搜索：

  • 首先根元素入队

  • 当队列不为空的时候

    1.  1.求当前队列的长度 Si
    2.   2.依次从队列中取 Si 个元素进行拓展，然后进入下一次迭代

  1. class Solution {
  2. public:
  3.     vector<vector<int>> levelOrder(TreeNode* root) { 
  4.      //初始化队列同时将第一层节点加入队列中，即根节点
  5.       queue<TreeNode*> az;
  6.       vector<vector<int>> sz;
  7.       if(root==nullptr)
  8.       {
  9.           return sz;
  10.       }
  11.       az.push(root);
  13.       //外层的while循环迭代的是层数
  14.       while(!az.empty())
  15.       {
  16.        //记录当前队列大小
  17.           int size=az.size();
  18.           vector<int> a;
  19.            //遍历这一层的所有节点
  20.           for(int i=0;i<size;i++)
  21.           { 
  22.               //从队首取出元素
  23.               TreeNode* node=az.front();
  24.               az.pop();
  25.               a.push_back(node->val);
  26.               if(node->left) az.push(node->left);
  27.               if(node->right)az.push(node->right);
  28.           }
  29.           sz.push_back(a);
  30.       }
  31.       return sz;
  32.     }
  33. };

大家请记住这个模板,后面的几个练习题，都是在这个上面稍作更改.

二叉树的层序遍历II

相对于上面的题目，我们就需要把数组翻转一下就好了.

  1. class Solution {
  2. public:
  3.     vector<vector<int>> levelOrderBottom(TreeNode* root) {
  4.          vector<vector<int>> az;
  5.          queue<TreeNode*> sz;
  6.           if(root==nullptr)
  7.           {
  8.               return az;
  9.           }
  10.           sz.push(root);
  11.            
  12.          while(!sz.empty())
  13.          {
  14.              vector<int> a;
  15.              int size=sz.size();
  16.              for(int i=0;i<size;i++)
  17.          {
  18.              TreeNode* node=sz.front();
  19.              sz.pop();
  20.              a.push_back(node->val);
  21.              if(node->left) sz.push(node->left);
  22.              if(node->right) sz.push(node->right);
  23.          }
  24.          az.push_back(a);
  25.          }
  26.          reverse(az.begin(),az.end());
  27.         return az;
  28.     }
  29. };

二叉树的右视图

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

  1. class Solution {
  2. public:
  3.     vector<int> rightSideView(TreeNode* root) {
  4.     vector<int> az;
  5.     queue<TreeNode*> sz;
  6.     if(root==nullptr)
  7.     {
  8.         return az;
  9.     }
  10.     sz.push(root);
  11.     while(!sz.empty())
  12.     {
  13.         int size=sz.size();
  14.         for(int i=0;i<size;i++)
  15.         {
  16.             TreeNode* node=sz.front();
  17.             sz.pop();
  18.             if(i==size-1)
  19.             {
  20.                 az.push_back(node->val);
  21.             }
  22.             if(node->left)sz.push(node->left);
  23.             if(node->right)sz.push(node->right);
  24.         }
  25.     }
  26.     return az;
  27.     }
  28. };

二叉树的层平均值

本题就是层序遍历的时候把一层求个总和在取一个均值。

  1. class Solution {
  2. public:
  3.     vector<double> averageOfLevels(TreeNode* root) {
  4.      vector<double> az;
  5.      queue<TreeNode*> sz;
  6.      if(root==nullptr)
  7. {
  8.     return az;
  9. }     sz.push(root);
  10.      while(!sz.empty())
  11.     {
  12.          double sum=0;
  13.         int size=sz.size();
  14.         for(int i=0;i<size;i++)
  15.         {
  16.             TreeNode* node=sz.front();
  17.             sz.pop();
  18.             sum+=node->val;
  19.             if(node->left)sz.push(node->left);
  20.             if(node->right)sz.push(node->right);
  21.         }
  22.         az.push_back(sum/size);
  23.     }
  24.      return az;
  25.     }
  26. };

N叉树的层序遍历

这题就是跟第一题基本一样的，只不过节点多了几个孩子

  1. class Solution {
  2. public:
  3.     vector<vector<int>> levelOrder(Node* root) {
  4.         vector<vector<int>> az;
  5.         queue<Node*> sz;
  6.         if(root==nullptr){
  7.             return az;
  8.         }
  9.         sz.push(root);
  10.         while(!sz.empty())
  11.         {
  12.             vector<int> a;
  13.            int size=sz.size();
  14.            for(int i=0;i<size;i++)
  15.            {
  16.                Node* node=sz.front();
  17.                sz.pop();
  18.                a.push_back(node->val);
  19.                for(int i=0;i<node->children.size();i++)
  20.                {
  21.                    if(node->children[i])
  22.                    sz.push(node->children[i]);
  23.                }
  24.            }
  25.            az.push_back(a);
  27.         }
  28.         return az;
  29.     }
  30. };

在每个树行中找最大值

  1. class Solution {
  2. public:
  3.     vector<int> largestValues(TreeNode* root) {
  4.     vector<int> az;
  5.     queue<TreeNode*> sz;
  6.     if(root==nullptr)
  7.     {
  8.         return az;
  9.     }
  10.     sz.push(root);
  11.     while(!sz.empty())
  12.     {
  13.         int size=sz.size();
  14.         int max=INT_MIN;
  15.        for(int i=0;i<size;i++)
  16.        {
  17.           TreeNode* node=sz.front();
  18.           sz.pop();
  19.           max=max>node->val?max:node->val;
  20.           if(node->left) sz.push(node->left);
  21.           if(node->right)sz.push(node->right);
  22.        }
  23.        az.push_back(max);
  24.     }
  25.     return az;
  26.     }
  27. };

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

回想一下二叉树的层次遍历，用广度优先实现的时候，就是层层遍历，每层临时遍历的节点都会放到一个队列中。队列中保存了第 i 层节点的信息，我们利用这个特点，将队列中的元素都串联一遍就可以了。

  1. class Solution {
  2.     public Node connect(Node root) {
  3.         if (root == null) {
  4.             return root;
  5.         }
  6.         
  7.         // 初始化队列同时将第一层节点加入队列中，即根节点
  8.         Queue<Node> queue = new LinkedList<Node>(); 
  9.         queue.add(root);
  10.         
  11.         // 外层的 while 循环迭代的是层数
  12.         while (!queue.isEmpty()) {
  13.             
  14.             // 记录当前队列大小
  15.             int size = queue.size();
  16.             
  17.             // 遍历这一层的所有节点
  18.             for (int i = 0; i < size; i++) {
  19.                 
  20.                 // 从队首取出元素
  21.                 Node node = queue.poll();
  22.                 
  23.                 // 连接
  24.                 if (i < size - 1) {
  25.                     node.next = queue.peek();
  26.                 }
  27.                 
  28.                 // 拓展下一层节点
  29.                 if (node.left != null) {
  30.                     queue.add(node.left);
  31.                 }
  32.                 if (node.right != null) {
  33.                     queue.add(node.right);
  34.                 }
  35.             }
  36.         }
  37.         
  38.         // 返回根节点
  39.         return root;
  40.     }
  41. }

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

和上题是完全一样的

  1. class Solution {
  2. public:
  3.     Node* connect(Node* root) {
  4.         if (root == nullptr) {
  5.             return root;
  6.         }
  7.         
  8.         // 初始化队列同时将第一层节点加入队列中，即根节点
  9.         queue<Node*> Q;
  10.         Q.push(root);
  11.         
  12.         // 外层的 while 循环迭代的是层数
  13.         while (!Q.empty()) {
  14.             
  15.             // 记录当前队列大小
  16.             int size = Q.size();
  17.             
  18.             // 遍历这一层的所有节点
  19.             for(int i = 0; i < size; i++) {
  20.                 
  21.                 // 从队首取出元素
  22.                 Node* node = Q.front();
  23.                 Q.pop();
  24.                 
  25.                 // 连接
  26.                 if (i < size - 1) {
  27.                     node->next = Q.front();
  28.                 }
  29.                 
  30.                 // 拓展下一层节点
  31.                 if (node->left != nullptr) {
  32.                     Q.push(node->left);
  33.                 }
  34.                 if (node->right != nullptr) {
  35.                     Q.push(node->right);
  36.                 }
  37.             }
  38.         }
  39.         
  40.         // 返回根节点
  41.         return root;
  42.     }
  43. };

二叉树的最大深度

这题前面有讲过， 可以参考这篇博客:力扣刷题之二叉树的最大深度_skeet follower的博客-CSDN博客

二叉树的最小深度

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

  1. class Solution {
  2. public:
  3.     int minDepth(TreeNode* root) {
  4.       queue<TreeNode*> az;
  5.       if(root==nullptr)
  6.       {
  7.           return 0;
  8.       }
  9.       int depth=0;
  10.       az.push(root);
  11.       while(!az.empty())
  12.       {
  13.           int size=az.size();
  14.           depth++;
  15.           for(int i=0;i<size;i++)
  16.           {
  17.               TreeNode* node=az.front();
  18.               az.pop();
  19.               if(node->left) az.push(node->left);
  20.               if(node->right)az.push(node->right);
  21.               if(node->right==nullptr&&node->left==nullptr)
  22.               {
  23.                   return depth;
  24.               }
  25.           }
  26.       }
  27.       return depth;
  28.     }
  29. };
标签： 算法 c语言 c++
本文转载自: https://blog.csdn.net/m0_58367586/article/details/124107118
版权归原作者 skeet follower 所有， 如有侵权，请联系我们删除。
登录后发布评论

“力扣刷题之二叉树的层序遍历”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？