LeetCode 104：二叉樹最大深度 - BFS 層序遍歷解法

LeetCode 104：二叉樹最大深度 - BFS 層序遍歷解法

題目

給定一棵二叉樹，求其最大深度（根節點到最遠葉子節點的最長路徑節點數）。

思路：BFS + 隊列逐層遍歷

• 用 Queue<TreeNode> 存儲當前層節點；
• 變量 size 記錄當前層節點數，處理完一層 depth++；
• 時間複雜度 O(n)，空間複雜度 O(w)（w 為最大層寬）。

參考代碼

public class MaximumDepthofBinaryTree104 {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int depth = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            depth++;
        }
        return depth;
    }
}

遞歸寫法（補充）

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

遞歸簡潔但深度極大時棧溢出風險；BFS 迭代更穩健。