程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

222. 完全二叉樹的節點個數 (Python)

編輯:Python

222. 完全二叉樹的節點個數

解題思路:

根據題意,完全二叉樹 的定義如下:

在完全二叉樹中,除了最底層節點可能沒填滿外,其余每層節點數都達到最大值,並且最下面一層的節點都集中在該層最左邊的若干位置

所以一棵樹的左子樹或右子樹為完全二叉樹,那麼部分子樹可以使用公式的方式直接計算出,這將節省通過逐層遞歸來計算節點的個數。

所以當一個節點的左子樹和右子樹高度相同時,那麼這棵樹為完全二叉樹。

對於完全二叉樹的左右子樹,其有一半肯定是完全的。

所以完全的部分使用公式計算。

綜合來講,遞歸深度為樹的高度是 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

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved