devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【代码随想录】——二叉树层序遍历_层序遍历二叉树代码

作者：盐析白兔 | 2024-06-14 03:02:08

赞

踩

层序遍历二叉树代码

之前介绍的是二叉树的深度优先遍历，接着是二叉树的另外一种遍历方式——层序遍历。

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

102. 二叉树的层序遍历

方法一：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<vector<int>> levelOrder(TreeNode* root) {
  15.         vector<vector<int>> res;
  16.         queue<TreeNode*> que;
  17.         if(root==NULL) return res;
  18.         que.push(root);
  19.  
  20.         while(!que.empty()){
  21.             int size=que.size();//变化的size，因为每次的que都在变化
  22.             vector<int> path;//每完成一层for循环，重新定义一个新path，不用清除之前的数据，满足了[[3],[9,20]]这种要求
  23.             //一次for循环，填充每一个path
  24.             for(int i=0;i<size;i++){
  25.                 TreeNode* node=que.front();
  26.                 que.pop();
  27.                 path.push_back(node->val);
  28.                 if(node->left) que.push(node->left);
  29.                 if(node->right) que.push(node->right);
  30.             } 
  31.             //for循环之后，将填好的path放进res中
  32.             res.push_back(path);
  33.         }
  34.         return res;
  35.     }
  36. };

方法二：相较于方法一，不同之处在于：for循环将每层填好的path放进res中之后，用path.clear()清除每层的path，就不用每一层申请一个新path。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<vector<int>> levelOrder(TreeNode* root) {
  15.         vector<int> path;
  16.         vector<vector<int>> res;
  17.         queue<TreeNode*> que;
  18.         if(root==NULL) return res;
  19.         que.push(root);
  20.  
  21.         while(!que.empty()){
  22.             int size=que.size();//变化的size，因为每次的que都在变化
  23.             //一次for循环，填充每一个path
  24.             for(int i=0;i<size;i++){
  25.                 TreeNode* node=que.front();
  26.                 que.pop();
  27.                 path.push_back(node->val);
  28.                 if(node->left) que.push(node->left);
  29.                 if(node->right) que.push(node->right);
  30.             } 
  31.             res.push_back(path);//for循环之后，将每层填好的path放进res中
  32.             path.clear();//清除每层的path
  33.         }
  34.         return res;
  35.     }
  36. };

107. 二叉树的层序遍历 II

该题与上题的不同之处在于：自底向上的层序遍历

其实只需要在上题的基础上，做一个reverse的操作即可。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<vector<int>> levelOrderBottom(TreeNode* root) {
  15.         vector<int> path;
  16.         vector<vector<int>> res;
  17.         queue<TreeNode*> q;
  18.         if(root==NULL) return res;
  19.         q.push(root);
  20.         while(!q.empty()){
  21.             int size=q.size();
  22.             for(int i=0;i<size;i++){
  23.                 TreeNode* node=q.front();
  24.                 q.pop();
  25.                 path.push_back(node->val);
  26.                 if(node->left) q.push(node->left);
  27.                 if(node->right) q.push(node->right);
  28.             }
  29.             res.push_back(path);
  30.             path.clear();
  31.         }
  32.         reverse(res.begin(),res.end());
  33.         return res;
  34.     }
  35. };

199. 二叉树的右视图

该题也是层序遍历的变形。其实就是将每层的最后一个元素放进res中返回即可 

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<int> rightSideView(TreeNode* root) {
  15.         vector<int> path;
  16.         vector<int> res;
  17.         queue<TreeNode*> q;
  18.         if(root==NULL) return res;
  19.         q.push(root);
  20.  
  21.         while(!q.empty()){
  22.             int size=q.size();
  23.             for(int i=0;i<size;i++){
  24.                 TreeNode* node=q.front();
  25.                 q.pop();
  26.                 path.push_back(node->val);
  27.                 if(node->left) q.push(node->left);
  28.                 if(node->right) q.push(node->right);
  29.             }
  30.             res.push_back(path[path.size()-1]);
  31.         }
  32.         return res;
  33.     }
  34. };

 637. 二叉树的层平均值

 在每一层for循环的时候将sum统计出来，然后在for循环结束之后就求平均值，将平均值放进res中。

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

 429. N 叉树的层序遍历

和二叉树的层序遍历区别在于：二叉树只有两个孩子节点，判断左右孩子不为空即可让他们入队。而N叉树有n个孩子节点，就需要借助for循环将每一个孩子判空然后入队。

  1.  for(int j=0;j<node->children.size();j++){//将node节点的孩子节点依次放进队列中
  2.                     if(node->children[j]) q.push(node->children[j]);
  3.                 }
  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     vector<Node*> children;
  7.  
  8.     Node() {}
  9.  
  10.     Node(int _val) {
  11.         val = _val;
  12.     }
  13.  
  14.     Node(int _val, vector<Node*> _children) {
  15.         val = _val;
  16.         children = _children;
  17.     }
  18. };
  19. */
  20.  
  21. class Solution {
  22. public:
  23.     vector<vector<int>> levelOrder(Node* root) {
  24.         vector<vector<int>> res;
  25.         vector<int> path;
  26.         queue<Node*> q;
  27.         if(root==NULL) return res;
  28.         q.push(root);
  29.  
  30.         while(!q.empty()){
  31.             int size=q.size();
  32.             for(int i=0;i<size;i++){
  33.                 Node* node=q.front();
  34.                 q.pop();
  35.                 path.push_back(node->val);
  36.                 for(int j=0;j<node->children.size();j++){//将node节点的孩子节点依次放进队列中
  37.                     if(node->children[j]) q.push(node->children[j]);
  38.                 }
  39.             }
  40.             res.push_back(path);
  41.             path.clear();
  42.         }
  43.         return res;
  44.     }
  45. };

515. 在每个树行中找最大值

 层序遍历大框架，每层for循环的时候，比较求出最大值，每层for循环结束后，将最大值放进res。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<int> largestValues(TreeNode* root) {
  15.         vector<int> res;
  16.         queue<TreeNode*> q;
  17.         if(root==NULL) return res;
  18.         q.push(root);
  19.  
  20.         while(!q.empty()){
  21.             int size=q.size();
  22.             int max=INT_MIN;
  23.             for(int i=0;i<size;i++){
  24.                 TreeNode* node=q.front();
  25.                 q.pop();
  26.                 if(node->val>max) max=node->val;
  27.                 if(node->left) q.push(node->left);
  28.                 if(node->right) q.push(node->right);
  29.             }
  30.             res.push_back(max);
  31.         }
  32.         return res;
  33.     }
  34. };

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

每层for循环，重新定义size，nodepre，node

在单层遍历时（包括i=0,i>0时）记录本层的头部节点，然后在遍历的时候（i>0时）让前一个节点指向本节点就可以了

然后每层for循环结束，本层最后一个节点指向NULL

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     Node* left;
  7.     Node* right;
  8.     Node* next;
  9.  
  10.     Node() : val(0), left(NULL), right(NULL), next(NULL) {}
  11.  
  12.     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
  13.  
  14.     Node(int _val, Node* _left, Node* _right, Node* _next)
  15.         : val(_val), left(_left), right(_right), next(_next) {}
  16. };
  17. */
  18.  
  19. class Solution {
  20. public:
  21.     Node* connect(Node* root) {
  22.         queue<Node*> q;
  23.         if(root!=NULL) q.push(root);
  24.  
  25.         while(!q.empty()){
  26.             //每层for循环，重新定义size，nodepre，node
  27.             int size=q.size();
  28.             Node* nodepre;
  29.             Node* node;
  30.  
  31.             for(int i=0;i<size;i++){
  32.                 if(i==0){
  33.                     nodepre=q.front();//取出每层的第一个节点
  34.                     q.pop();
  35.                     node=nodepre;
  36.                 }
  37.                 else{
  38.                     node=q.front();
  39.                     q.pop();
  40.                     nodepre->next=node;//本层前一个节点指向本节点
  41.                     nodepre=nodepre->next;
  42.                 } 
  43.                 if(node->left) q.push(node->left);
  44.                 if(node->right) q.push(node->right);
  45.             }
  46.             nodepre->next=NULL;//每层for循环结束，本层最后一个节点指向NULL
  47.         }
  48.         return root;
  49.     }
  50. };

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

这道题是二叉树，上一道题是完美二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道

每层for循环，重新定义size，nodepre，node

在单层遍历时（包括i=0,i>0时）记录本层的头部节点，然后在遍历的时候（i>0时）让前一个节点指向本节点就可以了

然后每层for循环结束，本层最后一个节点指向NULL

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     Node* left;
  7.     Node* right;
  8.     Node* next;
  10.     Node() : val(0), left(NULL), right(NULL), next(NULL) {}
  12.     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
  14.     Node(int _val, Node* _left, Node* _right, Node* _next)
  15.         : val(_val), left(_left), right(_right), next(_next) {}
  16. };
  17. */
  18.  
  19. class Solution {
  20. public:
  21.     Node* connect(Node* root) {
  22.         queue<Node*> q;
  23.         if(root!=NULL) q.push(root);
  24.  
  25.         while(!q.empty()){
  26.             int size=q.size();
  27.             Node* nodePre;
  28.             Node* node;
  29.             for(int i=0;i<size;i++){
  30.                 if(i==0){
  31.                     nodePre=q.front();
  32.                     q.pop();
  33.                     node=nodePre;
  34.                 }
  35.                 else{
  36.                     node=q.front();
  37.                     q.pop();
  38.                     nodePre->next=node;
  39.                     nodePre=nodePre->next;
  40.                 }
  41.                 if(node->left) q.push(node->left);
  42.                 if(node->right) q.push(node->right);
  43.             }
  44.             nodePre->next=NULL;
  45.         }
  46.         return root;
  47.     }
  48. };

 104. 二叉树的最大深度

最大深度即是二叉树的层数，层序遍历获得层数即可。

利用层序遍历的大框架，每层for循环结束之后sum++

最终while结束后，返回sum 

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int maxDepth(TreeNode* root) {
  15.         int sum=0;
  16.         queue<TreeNode*> q;
  17.         if(root!=NULL) q.push(root);
  18.         while(!q.empty()){
  19.             int size=q.size();
  20.             for(int i=0;i<size;i++){
  21.                 TreeNode* node=q.front();
  22.                 q.pop();
  23.                 if(node->left) q.push(node->left);
  24.                 if(node->right) q.push(node->right);
  25.             }
  26.             sum++;
  27.         }
  28.         return sum;
  29.  
  30.     }
  31. };

111. 二叉树的最小深度

层序遍历大框架，当node的左右孩子均为空的时候，说明到了最低点的一层，直接返回深度

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int minDepth(TreeNode* root) {
  15.         queue<TreeNode*> q;
  16.         int mindepth=0;
  17.         if(root!=NULL) q.push(root);
  18.         while(!q.empty()){
  19.             int size=q.size();
  20.             mindepth++;
  21.             for(int i=0;i<size;i++){
  22.                 TreeNode* node=q.front();
  23.                 q.pop();
  24.                 if(node->left) q.push(node->left);
  25.                 if(node->right) q.push(node->right);
  26.                 if(node->left==NULL && node->right==NULL) return mindepth;//当左右节点都为空，说明到了最低点的一层，直接返回
  27.             }
  28.         }
  29.         return mindepth;
  30.     }
  31. };

513. 找树左下角的值

层序遍历（队列） 

 //记录每一行的第一个元素即可，不断更新这个res就可以记录到最后一行的第一个元素

（定义了两个vector，将每一行的元素都放进去，最后返回vector的vector。这个办法就有点笨拙：return resback[resback.size()-1][0];）

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int findBottomLeftValue(TreeNode* root) {
  15.         queue<TreeNode*> q;
  16.         int res=0;
  17.         if(root!=NULL) q.push(root);
  18.         while(!q.empty()){
  19.             int size=q.size();
  20.             for(int i=0;i<size;i++){
  21.                 TreeNode* node=q.front();
  22.                 q.pop();
  23.                 if(i==0) res=node->val;//记录每一行的第一个元素即可，不断更新res就可以记录到最后一行的第一个元素
  24.                 if(node->left) q.push(node->left);
  25.                 if(node->right) q.push(node->right);
  26.             }
  27.         }
  28.         return res;
  29.     }
  30. };

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号