给每个leaf(包括null)编号

             A
           /   \
         B       C
       /  \     /  \
      D    E   F    #
      00   01  10   11

编号对应从root走到这个leaf的路径
e.g. 00 表示左->左， 01表示左->右

编号的二进制位数为树高(h), 最大id为2^h-1
e.g. 树高2 -> leafId in range [0 - 11], i.e. [0 - 2^2-1]
     树高3 -> leafId in range [0 - 111], i.e. [0 - 2^3-1]
     
然后就对leaf进行二分查找，找到id最大的non-null-leaf(上图中的F)
二分查找(左闭右闭)停止时, hi对应的就是这个id (why？看以下链接)
https://blog.nowcoder.net/n/738406717b8b4ffbb9a5f619b2b554ac

总共节点数 = # non-leaf + # leaf
         = 2^h-1 + (hi+1)
对应上面的例子 = 2^2-1 + (2+1) = 6


public class Solution {
    public int nodeNum(TreeNode head) {
      if (head == null) return 0;
      TreeNode t = head;
      int h = 0;  // tree height (i.e. num levels - 1)
      while (t.left != null) {
        t = t.left;
        h++;
      }
      
      if (h == 0) return 1; // single node tree
      
      // assign leaf (including nulls) with ids 0 - 2^h-1
      // binary search for the last non-null leaf
      int lo = 0, hi = (int) Math.pow(2, h)-1;
      while (lo <= hi) {
        int mid = lo + ((hi-lo) >> 1);
        
        if (isNullLeaf(mid, h, head)) {
          hi = mid - 1;
        } else {
          lo = mid + 1;
        }
      }
      int numNonLeaf = (int) Math.pow(2, h) - 1;
      // hi is the id of last non-null leaf
      // # leaf = hi + 1
      return numNonLeaf + hi + 1;
    }
  
    // Traverse from root to leaf based on the leafId.
    public boolean isNullLeaf(int leafId, int h, TreeNode head) {
      int bitmask = 1 << h-1;
      TreeNode cur = head;
      while (bitmask > 0) {
        boolean goRight = (bitmask & leafId) > 0;
        if (goRight) cur = cur.right;
        else cur = cur.left;
        bitmask >>= 1;
      }
      return cur == null;
    }
}