解題思路:
根據題意,完全二叉樹 的定義如下:
在完全二叉樹中,除了最底層節點可能沒填滿外,其余每層節點數都達到最大值,並且最下面一層的節點都集中在該層最左邊的若干位置。
所以一棵樹的左子樹或右子樹為完全二叉樹,那麼部分子樹可以使用公式的方式直接計算出,這將節省通過逐層遞歸來計算節點的個數。
所以當一個節點的左子樹和右子樹高度相同時,那麼這棵樹為完全二叉樹。
對於完全二叉樹的左右子樹,其有一半肯定是完全的。
所以完全的部分使用公式計算。
綜合來講,遞歸深度為樹的高度是 log N,每次遞歸所花費的時間就是 while 循環,需要 O(logN), 總的時間復雜度為 O(logN * 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: TreeNode) -> int:
if not root:
return 0
#記錄根結點的值,用於分別遍歷子樹的節點個數
leftRoot = root
rightRoot = root
left = 0
right = 0
#計算左子樹的個數
while leftRoot:
leftRoot = leftRoot.left
left += 1
#計算右子樹的個數
while rightRoot:
rightRoot = rightRoot.right
right += 1
#如果一個節點的左子樹和右子樹高度相同,那麼這棵樹為完全二叉樹
if(left == right):
return (2 ** left) - 1
#分別遞歸左右子樹,返回值加上根節點的個數 1
return self.countNodes(root.left) + self.countNodes(root.right) + 1