Medium

662. Maximum Width of Binary Tree

treedepth-first-searchbreadth-first-searchbinary-tree

在 LeetCode 上作答 ↗

解題說明

Maximum Width of Binary Tree

題目描述：給定一棵二元樹，求其最大寬度。最大寬度定義為所有層中，最左邊和最右邊的非空節點之間的長度（包含中間的空節點）。

解題思路：使用 BFS 層序遍歷，為每個節點指定一個位置編號。若父節點編號為 i，則左子節點為 2*i+1，右子節點為 2*i+2。每層的寬度就是該層最右邊節點的編號減去最左邊節點的編號再加 1。

為了避免編號溢位，每一層的編號都可以減去該層最小的編號（歸零化處理）。這樣即使樹很深，編號也不會溢位。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個節點恰好被訪問一次。

空間複雜度：O(n) — 佇列在最壞情況下可能存放 O(n) 個節點（完全二元樹的最後一層）。

虛擬碼

1. If root is null, return 0
2. Initialize queue with (root, index=0), maxWidth = 0
3. While queue is not empty:
   a. Record size of current level
   b. Get minIdx from front of queue (for normalization)
   c. For each node in current level:
      - Normalize index: idx -= minIdx
      - Track first and last index of this level
      - Enqueue left child with index 2*idx+1
      - Enqueue right child with index 2*idx+2
   d. maxWidth = max(maxWidth, last - first + 1)
4. Return maxWidth

其他解法

DFS 解法：使用 DFS 遍歷，用一個陣列記錄每層第一個被訪問的節點的位置編號。每次訪問節點時，用當前編號減去該層第一個節點的編號來計算寬度。時間 O(n)，空間 O(h)（h 為樹高）。DFS 的空間複雜度在平衡樹中優於 BFS，但在寬樹中 BFS 更直觀。

延伸思考

如果編號使用 int 而非 unsigned long long，在什麼情況下會溢位？如何避免？
能否用 DFS 實現？與 BFS 相比有何優劣？
如果要求的是每一層的寬度列表（而非最大值），該如何修改？

Maximum Width of Binary Tree — CaffeCode