Java 計算二叉樹深度與寬度：遞迴與層序遍歷完整實作

二叉樹節點定義

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;
    TreeNode(char val) { this.val = val; }
}

1. 最大深度（高度）—— 遞迴後序遍歷

深度定義：根節點到最遠葉節點的最長路徑上的節點數。空樹深度 0。

public class BinaryTreeMetrics {
    /** 遞迴計算最大深度 */
    public static int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return 1 + Math.max(leftDepth, rightDepth);
    }

    /** 迭代版（層序遍歷計數層數） */
    public static int maxDepthIterative(TreeNode root) {
        if (root == null) return 0;
        Queue queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            depth++;
        }
        return depth;
    }
}

2. 最大寬度—— 層序遍歷（BFS）

寬度定義：同一層級節點數的最大值。利用佇列逐層遍歷，每層遍歷前記錄佇列大小即為該層寬度。

import java.util.*;

public class BinaryTreeMetrics {
    /** 計算最大寬度 */
    public static int maxWidth(TreeNode root) {
        if (root == null) return 0;
        Queue queue = new ArrayDeque<>();
        queue.offer(root);
        int maxWidth = 1; // 至少根節點一層寬度為 1

        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // 當前層節點數
            maxWidth = Math.max(maxWidth, levelSize);

            // 遍歷當前層，將下一層節點入隊
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return maxWidth;
    }

    /** 進階：計算每層寬度詳情（含 null 佔位的完全二叉樹寬度） */
    public static int maxWidthWithNullPlaceholders(TreeNode root) {
        if (root == null) return 0;
        // 隊列存儲 (節點, 編號)，根編號 1，左 2*i，右 2*i+1
        Queue> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 1L));
        long maxWidth = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            long firstIdx = queue.peek().getValue();
            long lastIdx = firstIdx;
            for (int i = 0; i < levelSize; i++) {
                Pair pair = queue.poll();
                lastIdx = pair.getValue();
                TreeNode node = pair.getKey();
                if (node.left != null) queue.offer(new Pair<>(node.left, lastIdx * 2));
                if (node.right != null) queue.offer(new Pair<>(node.right, lastIdx * 2 + 1));
            }
            maxWidth = Math.max(maxWidth, lastIdx - firstIdx + 1);
        }
        return (int) maxWidth;
    }

    // 簡易 Pair 類
    static class Pair {
        private final K key; private final V value;
        Pair(K k, V v) { key = k; value = v; }
        K getKey() { return key; } V getValue() { return value; }
    }
}

測試驗證

public class TreeMetricsTest {
    public static void main(String[] args) {
        // 建構測試樹：
        //       A(1)
        //      / \
        //     B   C(2)
        //    /   / \
        //   D   E   F(3)
        //  /       / \
        // G       H   I(4)
        TreeNode root = new TreeNode('A');
        root.left = new TreeNode('B');
        root.right = new TreeNode('C');
        root.left.left = new TreeNode('D');
        root.right.left = new TreeNode('E');
        root.right.right = new TreeNode('F');
        root.left.left.left = new TreeNode('G');
        root.right.right.left = new TreeNode('H');
        root.right.right.right = new TreeNode('I');

        System.out.println("最大深度(遞迴): " + BinaryTreeMetrics.maxDepth(root)); // 4
        System.out.println("最大深度(迭代): " + BinaryTreeMetrics.maxDepthIterative(root)); // 4
        System.out.println("最大寬度(節點數): " + BinaryTreeMetrics.maxWidth(root)); // 3 (第3層: D,E,F)
        System.out.println("最大寬度(含null位置): " + BinaryTreeMetrics.maxWidthWithNullPlaceholders(root)); // 4 (第4層: G,null,H,I)
    }
}

複雜度分析

進階話題：直徑、平衡判斷、序列化

• 樹的直徑：任意兩節點最長路徑。後序遍歷計算左右深度和的最大值。
• 平衡二叉樹判斷：遞迴檢查每節點左右子樹高度差 ≤ 1，配合 -1 標記失衡提前返回。
• 序列化/反序列化：前序 + null 標記、層序遍歷、JSON 格式。

總結

• 深度：遞迴最簡潔（注意棧深），迭代 BFS 更安全適合深樹。
• 寬度：BFS 天然適配，標準版計節點數，進階版計完全二叉樹編號跨度（LeetCode 662 題型）。
• 統一遍歷：一次 BFS 可同時獲得深度、寬度、每層節點列表等資訊。