【LeetCode】102. 二叉树的层序遍历、107. 二叉树的层序遍历 II-阿里云开发者社区

【LeetCode】102. 二叉树的层序遍历、107. 二叉树的层序遍历 II

2023-10-11 29

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 102. 二叉树的层序遍历102. 二叉树的层序遍历给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）示例：

作者：小卢

专栏：《Leetcode》

喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）

示例：

思路：

我们这里利用一个队列q和levelsize(代表当前层数据的个数)

一开始我们先压入一个数值到q，并且levelsize为1，当q不为空会时，我们循环levesize次，每次取队头，取完后再判断取的元素有没有左右节点，有的话就压入，然后结束循环的时候更新levelsize

代码：

1. class Solution {
2. public:
3.     vector<vector<int>> levelOrder(TreeNode* root) {
4.         queue<TreeNode*>q;
5. int levelsize=0;
6. if(root)
7.         {
8.             q.push(root);
9.             levelsize=1;
10.         }
11.         vector<vector<int>>vv;
12. while(!q.empty())
13.         {
14.             vector<int>v;
15. while(levelsize--)
16.             {
17.                 TreeNode*front=q.front();
18.                 q.pop();
19.                 v.push_back(front->val);
20. if(front->left)
21.                 {
22.                     q.push(front->left);
23.                 }
24. if(front->right)
25.                 {
26.                     q.push(front->right);
27.                 }
28.             }
29.             levelsize=q.size();
30.             vv.push_back(v);
31.         }
32. return vv;
33.     }
34. };

107. 二叉树的层序遍历 II

题目：

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

示例：

思路：

和上题一样，就结尾多一个逆置。

代码：

1. class Solution {
2. public:
3.     vector<vector<int>> levelOrderBottom(TreeNode* root) {
4.         queue<TreeNode*>q;
5. int levelsize = 0;
6. if (root)
7.         {
8.             q.push(root);
9.             levelsize = 1;
10.         }
11.         vector<vector<int>>vv;
12. while (!q.empty())
13.         {
14.             vector<int>v;
15. while (levelsize--)
16.             {
17.                 TreeNode* front = q.front();
18.                 q.pop();
19.                 v.push_back(front->val);
20. if (front->left)
21.                 {
22.                     q.push(front->left);
23.                 }
24. if (front->right)
25.                 {
26.                     q.push(front->right);
27.                 }
28.             }
29.             levelsize = q.size();
30.             vv.push_back(v);
31.         }
32. reverse(vv.begin(),vv.end());
33. return vv;
34.     }
35. };

【LeetCode】102. 二叉树的层序遍历、107. 二叉树的层序遍历 II

102. 二叉树的层序遍历

107. 二叉树的层序遍历 II

热门文章

最新文章

相关电子书