LeetCode——二叉树的层序遍历

有礼貌的灰绅士

发布于 2023-04-17 20:15:58

1760

发布于 2023-04-17 20:15:58

文章被收录于专栏：C++与Linux的学习之路C++与Linux的学习之路

102. 二叉树的层序遍历 I

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

输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1] 输出：[[1]]

示例 3：

输入：root = [] 输出：[]

提示：

树中节点数目在范围 [0, 2000] 内 -1000 <= Node.val <= 1000

原题链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/

思路：这个只要用一个队列帮助就可以了：

先存储第一个结点。

然后访问第一个结点的左右子树，第一个结点出队。

区分层数采用vector<vector< int>>的方式，用循环，里面的vector< int>是一层，放入一层二叉树的数据，然后再次进入就是下一层了。代码：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>arr;
        queue<TreeNode*>q;
        int qsize = 0;//记录结点数用的
        if(root)
        {
            q.push(root);//入队
            qsize = 1;//结点数1
        }
        while(!q.empty())
        {
            vector<int>ar;//一层结点的数据储存
            while(qsize--)//走完层数和结点也有关
            {
                TreeNode*p = q.front();
                q.pop();//出队
                ar.push_back(p->val);//让数据进入
                if(p->left)//不为空入队
                    q.push(p->left);
                if(p->right)
                    q.push(p->right);
            }
            arr.push_back(ar);//将这一层的数据放入arr中
            qsize = q.size();//下一层的结点个数
        }
        return arr;
    }
};

107. 二叉树的层序遍历 II

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

输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1] 输出：[[1]]

示例 3：

输入：root = [] 输出：[]

提示：

树中节点数目在范围 [0, 2000] 内 -1000 <= Node.val <= 1000

原题链接：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/

思路：

这道题只要将上面数组反转一下就可以了。代码：

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>>arr;
        queue<TreeNode*>q;
        int qsize = 0;//记录结点数用的
        if(root)
        {
            q.push(root);//入队
            qsize = 1;//结点数1
        }
        while(!q.empty())
        {
            vector<int>ar;//一层结点的数据储存
            while(qsize--)//走完层数和结点也有关
            {
                TreeNode*p = q.front();
                q.pop();//出队
                ar.push_back(p->val);//让数据进入
                if(p->left)//不为空入队
                    q.push(p->left);
                if(p->right)
                    q.push(p->right);
            }
            arr.push_back(ar);//将这一层的数据放入arr中
            qsize = q.size();//下一层的结点个数
        }
        reverse(arr.begin(),arr.end());
        return arr;
    }
};