Leetcode-222题:Count|Leetcode-222题:Count Complete Tree Nodes
题目：Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:思路：如果知道一个子树是完全二叉树，并且其深度为h，那么这棵子树所包含的节点个数便为2^h-1。否则便需递归求其左右子树的节点个数。
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
【Leetcode-222题:Count|Leetcode-222题:Count Complete Tree Nodes】代码：
def getHightRight(self, root):
if root == None:
return 0
high = 0
while root != None:
high += 1
root = root.right
return highdef getHightLeft(self, root):
if root == None:
return 0
high = 0
while root != None:
high += 1
root = root.left
return highdef countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
l_high = self.getHightLeft(root.left)
r_high = self.getHightRight(root.right)
if l_high == r_high:
return 2**(l_high+1)-1
else:
return self.countNodes(root.left)+self.countNodes(root.right)+1
推荐阅读
- #|2022最新前端面试题(HTML/CSS篇 近万字含解答)
- 微信小程序毕业设计项目|微信小程序毕业设计题目计算机维修服务+后台管理系统|前后分离VUE.js
- 管理会计简答题
- QT|QT利用 QFile, QTextStream写入、读取文件时的换行问题
- 【面试题】Vue中的$router|【面试题】Vue中的$router 和 $route的区别
- 面试笔试题|Https的加密原理是什么（）
- Python每日一练|Python每日一练（牛客新题库）——第26天（面向对象）
- 微信小程序|微信小程序面试题大全（持续更新）
- TCP和UDP常见面试题(全面)
- 007写作遇到的问题，另推荐书目《皮囊》