数据结构与算法-二叉树-层次遍历I

二叉树层次遍历I

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

示例 1：

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

思路：提到层次遍历，首先想到的就是用队列，首先将头节点放入队列中，然后出队，将出队节点的左节点和右节点分别入队，一直重复该操作，直到队列为空。

但是该题要求输出要求每一层放到一个List中，所以需要在原有基础上，做一些调整。通过获取队列的大小，来判断哪些节点是在同一层

解题：

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

我最开始想到的思路就是在每一层结束的时候添加一个标记位，来表示该层的结束。实现代码如下：

个人觉得没什么问题，但是最终力扣判定超时。不知道为啥。

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) {
            queue.add(root);
            queue.add(new TreeNode(Integer.MAX_VALUE));
        }
        while(!queue.isEmpty()) {
            List<Integer> arr = new ArrayList<>();
            while (!queue.isEmpty() && queue.peek().val != Integer.MAX_VALUE) {
                TreeNode poll = queue.poll();
                arr.add(poll.val);
                if(poll.left != null) {
                    queue.add(poll.left);
                }
                if(poll.right != null) {
                    queue.add(poll.right);
                }
            }
            queue.add(new TreeNode(Integer.MAX_VALUE));
            if(arr.size()>0) {
                res.add(arr);
            }
            queue.poll();
        }
        
        return res;

    }