LeetCode 662. 二叉樹的最大寬度

記錄一次刷題的感悟。這道題目是我人生第一次面試的時候的手撕題目，但臨場的時候面試官沒有為難我，他考察的問題是求二叉樹的最大寬度，但是不需要考慮 null 結點，也就是空的結點不計入寬度當中。

當我再次刷到這道題，發現當初面試的時候自己的理解有問題，計算寬度的時候應該考慮 null 結點，比如對于下面這樣一棵樹：

這棵樹的最大寬度就是 7，而不是 2。

有了這一層限制，這道題目就具有了一定的難度，下面開始分析解這道題的思路。

題目描述

思路

我們使用 BFS 來解這道問題。

其實從后驗的角度來說，這道題目沒有什么難度，但是難就難在臨場想不到這道題的正確思路。

正確的思路其實是，新開一個數據結構，同時保存二叉樹的結點以及當前節點的編號。每一次計算一層的最大的寬度時，計算隊列頭和隊列尾兩個二叉樹結點之間編號的差值。

二叉樹結點的編號計算規則如下：對于當前的結點$i$，它的左孩子結點編號為$2\times i$，右孩子結點編號為$2\times i+1$。基于二叉樹結點的編號，我們甚至可以在一個數組當中存儲二叉樹。堆排序正是利用了這條性質，在數組當中利用二叉樹建堆來實現最大堆或最小堆。

Golang 代碼

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
type pair struct {node  *TreeNodeindex int
}func widthOfBinaryTree(root *TreeNode) int {ans := 1q := []pair{}q = append(q, pair{root, 1})for len(q) > 0 {ans = max(ans, q[len(q) - 1].index -  q[0].index + 1)currLen := len(q)for i := 0; i < currLen; i ++ {p := q[0]; q = q[1:]if p.node.Left != nil {q = append(q, pair{p.node.Left, 2 * p.index})}if p.node.Right != nil {q = append(q, pair{p.node.Right, 2 * p.index + 1})}}}return ans
}