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