主題
題目連結(jié)：
題目意譯：
給定一棵二元樹的根節(jié)點 root，回傳給定的樹之最大寬度。
一棵樹的最大寬度為所有階層中的寬度值最大者。
一個階層之寬度定義為兩端的節(jié)點（最左以及最右的非空節(jié)點）之間的長度，其中在完全二元樹（Complete Binary Tree）中延伸到該階層中存在於兩端的節(jié)點之間的空節(jié)點也將會算在長度值之內(nèi)。
（原文：
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.
where 之後的子句不論怎麼翻我都覺得很怪，希望有英文大大可以幫忙潤飾。這個整個句子的意思在下面的解題思路有詳細(xì)的解釋。）
保證答案之值位於 32 位元有號整數(shù)的範(fàn)圍中。
限制：
樹中的節(jié)點數(shù)位於範(fàn)圍 [1, 3000] 中。
-100 ≦ Node.val ≦ 100
範(fàn)例測資：
範(fàn)例 1：
輸入： root = [1,3,2,5,3,null,9]
輸出： 4
解釋： 最大寬度存在於第三階層，其長度為 4（即 5, 3, null, 9）。
範(fàn)例 2：
輸入： root = [1,3,2,5,null,null,9,6,null,7]
輸出： 7
解釋： 最大寬度存在於第四階層，其長度為 7（即 6, null, null, null, null, null, 7）。
範(fàn)例 3：
輸入： root = [1,3,2,5]
輸出： 2
解釋： 最大寬度存在於第二階層，其長度為 2（即 3, 2）。
解題思維：
完全二元樹可以一層一層由上至下、由左至右地依序從 1 編號到 n（其中 n 代表著樹的節(jié)點數(shù)）而且不會跳號（參見維基頁面）。而且可以看到從根節(jié)點（編號 1）開始，往左子樹編號就乘以 2、往右子樹編號就乘以 2 並加上 1，也就是說從根節(jié)點走到某個節(jié)點的路徑與編號是一對一的。
而題目敘述中有標(biāo)注「原文」的部分的意思即是指，我們將給定的樹補成一棵完全二元樹的時候，例如範(fàn)例 2 將會變成下圖
（其中每個圓圈一樣代表著一個節(jié)點，內(nèi)部沒有寫數(shù)字的是空節(jié)點。而每個圓圈右上的數(shù)字代表按照完全二元樹之編號）
在每一層的兩側(cè)端點中間可能會多出一些空節(jié)點（例如上圖中第四層的 6 和 7 這兩個節(jié)點之間多了五個空節(jié)點）。
而我們把這些空節(jié)點拿掉之後（也就是回到原本的樹），實際上完全二元樹的編號還是可以保留下來（因為先前提到路徑可以決定編號；反過來說，編號也可以決定路徑）。
因此根據(jù)這個路徑?jīng)Q定編號的方式我們便可以直接從根節(jié)點開始進行深度優(yōu)先搜尋（Depth First Search，DFS）來算出每個節(jié)點的編號。然後對於每一層我們找出該層編號最小值 m 以及最大值 M，而 M - m + 1 即是該層的寬度。取當(dāng)中最大者即是所求最大寬度。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
