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

水深无声 2024-03-16 13:16 73阅读 0赞

>  作者：小卢
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![7d63d497b5114103b3dd7633a1ba4731.jpeg][]
> 
> --------------------

## 102. 二叉树的层序遍历 ##

[102. 二叉树的层序遍历][102.]

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

示例：![f7499233731047c8aa2fb31fc95cbac1.png][]

思路：

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

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

代码：

class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            queue<TreeNode*>q;
            int levelsize=0;
            if(root)
            {
                q.push(root);
                levelsize=1;
            }
            vector<vector<int>>vv;
            while(!q.empty())
            {
                vector<int>v;
                while(levelsize--)
                {
                    TreeNode*front=q.front();
                    q.pop();
                    v.push_back(front->val);
                    if(front->left)
                    {
                        q.push(front->left);
                    }
                    if(front->right)
                    {
                        q.push(front->right);
                    }
                }
                levelsize=q.size();
                vv.push_back(v);
            }
            return vv;
        }
    };

## 107. 二叉树的层序遍历 II ##

[107. 二叉树的层序遍历 II][107. _ II]

题目：

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

示例：

![f50cb94e821446c98f6b676633266cfd.png][]

思路：

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

代码：

class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            queue<TreeNode*>q;
            int levelsize = 0;
            if (root)
            {
                q.push(root);
                levelsize = 1;
            }
            vector<vector<int>>vv;
            while (!q.empty())
            {
                vector<int>v;
                while (levelsize--)
                {
                    TreeNode* front = q.front();
                    q.pop();
                    v.push_back(front->val);
                    if (front->left)
                    {
                        q.push(front->left);
                    }
                    if (front->right)
                    {
                        q.push(front->right);
                    }
                }
                levelsize = q.size();
                vv.push_back(v);
            }
            reverse(vv.begin(),vv.end());
            return vv;
        }
    };

[7d63d497b5114103b3dd7633a1ba4731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/88154f27431a455b9062deb660e4d7cc.png
[102.]: https://leetcode.cn/problems/binary-tree-level-order-traversal/
[f7499233731047c8aa2fb31fc95cbac1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/1f653630a3ca48c1a05c772226c84cb5.png
[107. _ II]: https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
[f50cb94e821446c98f6b676633266cfd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/903a5e639c6646c7950237b37e43a12b.png