Description
給定一棵二元樹的根節點，回傳樹的最大寬度。最大寬度是所有層中，最左和最右非 null 節點之間的寬度（包含中間的 null 節點）。
Example:
Input: root = [1,3,2,5,3,null,9] Output: 4
Intuition#
為每個節點編號，每層的寬度就是最右編號減最左編號加一。
- 用完全二元樹的索引方式：根為 0，左子為 2i+1，右子為 2i+2
- 每一層記錄最左和最右的索引，差值 + 1 就是該層寬度
- 注意：索引可能溢位，需要做偏移處理（每層減去該層最左的索引）
Approaches#
1: BFS + 索引編號#
- 概念: 層序遍歷，為每個節點編號，每層計算最左與最右索引的差
- 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun widthOfBinaryTree(root: TreeNode?): Int {
if (root == null) return 0
var maxWidth = 0
val queue: Queue<Pair<TreeNode, Int>> = LinkedList()
queue.offer(root to 0)
while (queue.isNotEmpty()) {
val size = queue.size
val leftIdx = queue.peek().second
var rightIdx = leftIdx
for (i in 0 until size) {
val (node, idx) = queue.poll()
val normalizedIdx = idx - leftIdx // 防止溢位
rightIdx = normalizedIdx
node.left?.let { queue.offer(it to normalizedIdx * 2 + 1) }
node.right?.let { queue.offer(it to normalizedIdx * 2 + 2) }
}
maxWidth = maxOf(maxWidth, rightIdx + 1)
}
return maxWidth
}
}⭐ 2: DFS + 記錄每層最左索引#
- 概念: DFS 遍歷，用列表記錄每一層第一次遇到的索引（最左），後續節點的索引減去最左索引即為寬度
- 時間複雜度:
O(n) - 空間複雜度:
O(h)，h 為樹高
class Solution {
private var maxWidth = 0
private val leftMost = mutableListOf<Long>()
fun widthOfBinaryTree(root: TreeNode?): Int {
maxWidth = 0
leftMost.clear()
dfs(root, 0, 0L)
return maxWidth
}
private fun dfs(node: TreeNode?, depth: Int, index: Long) {
if (node == null) return
if (depth == leftMost.size) {
leftMost.add(index)
}
val width = (index - leftMost[depth] + 1).toInt()
maxWidth = maxOf(maxWidth, width)
dfs(node.left, depth + 1, index * 2 + 1)
dfs(node.right, depth + 1, index * 2 + 2)
}
}🔑 Takeaways#
- Pattern: 利用完全二元樹的索引編號來計算寬度，本質是數學映射
- 關鍵技巧: 每層索引需要做偏移（減去該層最左索引），避免深度較大時索引溢位