222_完全二叉树的节点个数

类型：树

• 222. 完全二叉树的节点个数 💛 ⭐

  https://leetcode-cn.com/problems/count-complete-tree-nodes/

  ❓ 给你一棵完全二叉树，求结点个数。

  💡 二分查找

  根据完全二叉树的性质，其最左边的结点一定位于最底层，因此我们从根结点出发一直向左，就可以得到树的高度 h。

  根据完全二叉树的性质，其高度为 h，则结点数量在 [2^h， 2^(h+1) - 1] 的范围内。关键还是在于最底层。

  此题的一个关键应用在于，如何通过位运算得出编号为 k 的节点在完全二叉树中的路径。

  class Solution:
  
      def countNodes(self, root: TreeNode) -> int:
          if not root:
              return 0
  
          depth = -1
          node = root
          while node:
              depth += 1
              node = node.left
  
          minNo = 2 ** depth
          maxNo = 2 ** (depth + 1) - 1
  
  				# check 编号为 num 的结点是否存在
          def check(node, num):
              path = []
              while num:
                  path.insert(0, num & 1)
                  num = num >> 1
              for direction in path[1:]:                
                  if direction == 0:
                      if not node.left:
                          return False
                      else:
                          node = node.left
                  else:
                      if not node.right:
                          return False
                      else:
                          node = node.right
              return True
  
          while minNo <= maxNo:
              midNo = (minNo + maxNo) // 2
              if check(root, midNo):
                  minNo = midNo + 1
              else:
                  maxNo = midNo - 1
  
          return maxNo