建立一个完全二叉树,能够统计二叉树的叶子结点的个数,求二叉树的深度的python代码
时间: 2024-05-11 10:15:07 浏览: 95
以下是Python代码实现:
```python
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
left_depth = self.get_depth(root.left)
right_depth = self.get_depth(root.right)
if left_depth == right_depth:
return 2 ** left_depth + self.countNodes(root.right)
else:
return 2 ** right_depth + self.countNodes(root.left)
def get_depth(self, root: TreeNode) -> int:
if not root:
return 0
depth = 0
while root:
depth += 1
root = root.left
return depth
```
对于一个完全二叉树,可以利用完全二叉树的性质来统计叶子节点的个数和深度。可以通过递归的方式来实现,如果左子树和右子树的深度相同,那么左子树一定是满二叉树,可以通过公式 $2^h-1$ 来计算左子树的节点数,同时递归计算右子树的节点数;如果左子树的深度比右子树深度大一,那么右子树一定是满二叉树,同样可以通过公式 $2^h-1$ 来计算右子树的节点数,同时递归计算左子树的节点数。对于深度的计算,可以从根节点一直往左子树遍历,得到深度。
阅读全文