【Check 48】2024-04-10 - 102. 二叉树的层序遍历

[larscheng]

102. 二叉树的层序遍历

• 关联 #147

[larscheng]

思路

广度优先遍历

• 用队列记录根节点，遍历队列节点的同时，向队列中添加下一层的节点，如此往复

代码

class Solution {
    //O(n)/O(n)
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root==null){
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left!=null){
                    queue.add(node.left);
                }
                if (node.right!=null){
                    queue.add(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)