Solution

countNodes3

因 complete binary tree 特性，假設左子樹的高等於右子樹的高，則能確定左子樹被填滿，如下範例一。

範例一

     1
   /   \
  2     3
 / \   /
4   5 6

若左子樹高不等於右子樹高，則代表左子樹被填滿，如下範例二。

範例二

     1
   /   \
  2     3
 /
4

如要計算被填滿的樹的節點數，可以用 2^h -1 得到結果，但因為我們是用 root 的左子樹與右子數做比較，所以以範例一來看，如果我要計算 root(1) 與其左子樹的節點數量，可以用 2^(root高 - 1) 得到結果。以範例二來看，要計算 root(1) 與其右子樹的節點數量，可以用 2^(root高 - 2) 得到結果。

我們解析一下程式碼邏輯。
第53行：前面有先計算 root 高度 h，因為我們會向 root 的左子樹或右子樹迭代，所以只需遍歷 h 次即可。
第5457行：若右子樹的高等於 h-1 即代表左子樹與右子樹高度相同（與範例一相同情況），這時可以加上 2^(h-1) 並往右子樹迭代。
第5961行：為右子樹的高度等於 h-2 即代表左子樹高度與右子樹高度相差1（與範例二相同情況），這時可以加上 2^(h-2) 並往左子樹迭代。

countNodes4

與 countNodes3 相同思路，只是換用 recursion 解。