題目描述
給你一棵 完全二叉樹 的根節點 root ，求出該樹的節點個數。
完全二叉樹 的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其餘每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若幹位置。若最底層為第 h 層，則該層包含 1~ 2h 個節點。
示例 1：
輸入：root = [1,2,3,4,5,6]
輸出：6
示例 2：
輸入：root = []
輸出：0
示例 3：
輸入：root = [1]
輸出：1
提示：
樹中節點的數目範圍是[0, 5 * 104]
0 <= Node.val <= 5 * 104
題目資料保證輸入的樹是 完全二叉樹
對于沒有限制的二叉樹而言，可以很簡單地想到使用下面這個遞歸的解法：
但這是一個普适的解法，對于此題給的完全二叉樹的特點沒有利用起來，進一步考慮如何使用完全二叉樹的特點更快解出此題。
首先需要明确完全二叉樹的定義：它是一棵空樹或者它的葉子節點隻出在最後兩層，若最後一層不滿則葉子節點隻在最左側。
再來回顧一下滿二叉的節點個數怎麼計算，如果滿二叉樹的層數為h，則總節點數為：2^h - 1.
那麼我們來對 root 節點的左右子樹進行高度統計，分别記為 left 和 right，有以下兩種結果：
left == right。這說明，左子樹一定是滿二叉樹，因為節點已經填充到右子樹了，左子樹必定已經填滿了。是以左子樹的節點總數我們可以直接得到，是 2^left - 1，加上目前這個 root 節點，則正好是 2^left。再對右子樹進行遞歸統計。 left != right。說明此時最後一層不滿，但倒數第二層已經滿了，可以直接得到右子樹的節點個數。同理，右子樹節點 +root 節點，總數為 2^right。再對左子樹進行遞歸查找。
簡單地說，<code>left == right</code>,左子樹是滿二叉樹；<code>left !=right</code>，右子樹是滿二叉樹
關于如何計算二叉樹的層數，可以利用下面的遞歸來算，當然對于完全二叉樹，可以利用其特點，不用遞歸直接算，具體請參考最後的完整代碼。
規定根節點位于第 0 層，完全二叉樹的最大層數為 h。
如何判斷第 k 個節點是否存在呢？如果第 k 個節點位于第 h 層，則 k 的二進制表示包含 h+1 位，其中最高位是 1，其餘各位從高到低表示從根節點到第 k 個節點的路徑，0 表示移動到左子節點，1 表示移動到右子節點。通過位運算得到第 k 個節點對應的路徑，判斷該路徑對應的節點是否存在，即可判斷第 k個節點是否存在。
拓展思路不易想到了解難度大，作為一種參考思路即可，重點掌握前面的簡潔思路。
等比數列求和公式