二叉树的层序遍历-一一网

Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

一、题目

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
复制代码

示例 2：

输入：root = [1]
输出：[[1]]
复制代码

示例 3：

输入：root = []
输出：[]
复制代码

二、题解

1.解读
需要按层遍历二叉树，并且要区分下每一层的节点。

方法一
既然是按层遍历所以可以想到用广度优先搜索，广度优先搜索是按树结构的层层遍历，需要一个栈来辅助，大概思路为先将树的根节点入栈，然后循环取出栈元素，首先是根节点（取出第一层），如果当前根节点的左子树和右子树不为空的话，就入栈（放入第二层）；然后再重复取出栈元素节点，再放入栈元素节点下的左子树和右子树。具体的因为要区分层与层的节点，所以取出栈元素之前需要记录当前层有多少节点，然后就可以按层取出节点了，这样就能区分获取每一层的节点了。首先需要一个res集合存储结果集，然后需要一个queue队列辅助遍历，然后将root根节点放入队列queue，如果队列不为空就循环取出队列元素，本来每次循环是只取一个元素，现在要按层取出，所以先记录当前队列的元素节点数量size，根据size的大小，我们再循环队列取出size个节点node，同时判断当前节点node的左子树和右子树，如果存在的话就再将node的子树放入队列，最后获取到size个节点之后就是当前层的节点，记录到结果集中，然后继续下一层的循环。

三、代码
方法一
Java代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 1; i <= size; ++i) {
                TreeNode tree = queue.poll();
                level.add(tree.val);
                if (tree.left != null) {
                    queue.offer(tree.left);
                }
                if (tree.right != null) {
                    queue.offer(tree.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}
复制代码