給出一個完全二叉樹，求出該樹的節點個數，
說明：
完全二叉樹的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其余每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若干位置，若最底層為第 h 層，則該層包含 1~ 2h 個節點，
示例:
輸入:
1
/
2 3
/ \ /
4 5 6
輸出: 6
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-complete-tree-nodes
思路：
1.先遞回計算出完全二叉樹的高度h，除了最后一層葉子結點外，前h-1層的結點總數為2^(h-1)-1，
2.接著計算最后一層葉子結點個數，判斷是葉子結點的條件為：該結點的左結點為空且右結點也為空，
這里需要增加一個條件：當前高度level，因為倒數第二層也可能會出現葉子結點，而我們只需要計算最后一層結點，倒數第二層的結點在第一步已經計算進去了，如果不增加當前層高度為level=h這個判斷的話會多計算一次倒數第二層的葉子結點，
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: #計算沒有節點的情況
return 0
def height(tree): #計算樹的高度
if not tree:
return 0
else:
return max(height(tree.left),height(tree.right))+1
self.h=height(root) #h為樹的高度
self.count=0
#最后一層節點個數
def nodecount(tree , level):
if not tree:
return 0
if not tree.left and not tree.right and level==self.h:
self.count+=1
nodecount(tree.left,level+1) #左節點的遞回
nodecount(tree.right,level+1) #右節點的遞回
return self.count
c=nodecount(root,1)
allnodes=pow(2,self.h-1)-1+c
return allnodes
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/227656.html
標籤：python