Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.
Design an algorithm that runs in less than O(n) time complexity.
Example 1:
Input: root = [1,2,3,4,5,6] Output: 6
Example 2:
Input: root = [] Output: 0
Example 3:
Input: root = [1] Output: 1
Constraints:
- The number of nodes in the tree is in the range
[0, 5 * 104]. 0 <= Node.val <= 5 * 104- The tree is guaranteed to be complete.
題目要求一棵完全二叉樹的節點個數，所謂完全二叉樹就是樹中除了最后一層其他每層的節點都是滿的，而最后一層的節點是集中在左部即從左到右挨個分布的，根據完全二叉樹的特點，我們可以直接算出各層（除了最后一層）的節點個數，
對一個高度為h（第一層高度為1）的完全二叉樹，前h - 1層的節點個數是2^0 + 2^1 + ... + 2^(h - 2) = 2^(h - 1) - 1，而最后一層由于可能不是滿的，節點個數并確定，但可以確定個數是在1到2^(h-1)范圍內，也就說只要能求出最后一層節點個數，就能知道整棵樹的節點總個數，
因此本題就變成了求最后一層節點個數，它是1到2^(h-1)范圍內的某個數，這很容易想到用二分查找法，把區間[1, 2^(h-1)]從中間分成左右兩個區間，然后判斷中點第(1 + 2^(h-1))//2個節點是否存在，如果存在說明左半區間是滿點，則繼續在右半區間查找；如果不存在說明左半區間不是滿的而右半區間肯定是空的，則繼續在左半區間查找，
到此，本題該如何用二分查找法已經很明確了，難點就變成了該如何快速地判斷最后一層的某一個節點是存在，我們會發現一棵樹（h > 1）的最后一層的中間節點是根節點的左子樹的最右邊的那個節點，抓住這個特點就可以快速地判斷最后一層的中間節點是否存在，
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
h = self.height(root)
if h <= 1:
return h
#前h-1層的總個數
res = 2 ** (h - 1) - 1
#最后一層個數介于[1, 2 ** (h - 1)]之間
l, r = 1, 2 ** (h - 1)
while l <= r:
#并判斷最后一層中間那個節點是否存在
mid = l + (r - l) // 2
if self.isExist(root, h): #如存在則繼續查找右半區間即右子樹
l = mid + 1
if root:
root = root.right
else: #如不存在則繼續查找左半區間即左子樹
r = mid - 1
if root:
root = root.left
#左右半區間分別對應于左右子樹，子樹高度減1
h -= 1
#查找到最后，l是最后一層第一不存在的節點，因此最后一層個數是l - 1
return res + l - 1
def height(self, root):
res = 0
while root:
root = root.left
res += 1
return res
#判斷一棵高度為h的樹的最后一層的中間節點是否存在
def isExist(self, root, h):
#只有一層時即最后一層，直接判斷該節點是否存在
if h == 1:
return root != None
#如果不只一層則最后一層的中間節點是左子樹的最靠右的那個節點
root = root.left
h -= 1
for i in range(h - 1):
root = root.right
return root != None
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/390584.html
標籤：其他
上一篇：大數階乘，有趣