## 題解

### Brute force

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return self.countNodes(root.left) + self.countNodes(root.right) + 1

### Binary Search + Bit Manipulation

#### 1. 找出 Tree 有幾層

只要一直遍歷左子樹到底就可以算出樹的層數

### 2. 使用二進位定位節點路徑

1. 先找出要找節點的 level ，套入公式 node = 1 << (level - 1)
2. 使用 node & target 得到 0 或 1，0 代表 left，1 代表 right
3. 每次 node 比較完 target 都要向右移一位 node >>= 1
4. 直到 node == 0 時停止尋找節點
5. 如果節點存在，則會在 node == 0 時走到節點上，判斷指針是否為 null 即可


#### 3. 進行二分查找定位最大位置

如果樹的層數 為 3 我們可以知道節點:

最小總數為 2 ** (3-1) = 4
最大總數為 2 ** (3 + 1) - 1 = 7

所以我們要查找的範圍就會是在 4 - 7 之間，找出最大並且已存在的節點，這樣子時間複雜度就可以降低到 avg. O(logn)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        def find_height(root):
            output = 0
            while root.left:
                output += 1
                root = root.left
            return output
    
        def binary_search(root,height):
            low = (1 << height)
            high = (1 << (height + 1)) - 1 
            while low < high:
                mid = low + (high - low + 1) // 2 # 要 +1
                if find(root,mid,height):
                    low = mid
                else:
                    high = mid - 1
            return low
            
        def find(root,target,height):
            current_node = 1 << (height - 1)
            node = root
            while node and current_node > 0:
                if (current_node & target) == 0:
                    node = node.left
                else:
                    node = node.right
                current_node = current_node >> 1
            return node is not None
        
        if not root:
            return 0
        height = find_height(root)
        return binary_search(root,height)