二叉树 - LeetCode 102. 二叉树的层序遍历

二叉树的层序遍历又称为二叉树的广度优先搜索（BFS）。BFS 通常借助队列的先入先出特性来实现。

image.png

算法流程：

image.png

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root); // 入队
        while (!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            // 遍历队列
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll(); // 出队
                tmp.add(node.val);
                if (node.left != null) queue.add(node.left); // 左子树入队
                if (node.right != null) queue.add(node.right); // 右子树入队
            }
            res.add(tmp);
        }
        return res;
    }
}

image.png image.png

复杂度分析：

image.png

✅ LeetCode 104. 二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        List<List<Integer>> res = new ArrayList<>(); 
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root); // 入队
        while (!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            // 遍历队列
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll(); // 出队
                tmp.add(node.val);
                if (node.left != null) queue.add(node.left); // 左子树入队
                if (node.right != null) queue.add(node.right); // 右子树入队
            }
            res.add(tmp);
        }
        return res.size();
    }
}

• 时间复杂度 O(N) ： N 为树的节点数量，计算树的深度需要遍历所有节点。
• 空间复杂度 O(N) ： 最差情况下（当树平衡时），队列 queue 同时存储 N/2 个节点。