题目给定一棵二叉树,计算该二叉树的深度、总节点个数和叶子节点个数。
时间: 2024-01-23 13:49:01 浏览: 245
好的,你可以将这些问题分开来回答。首先,计算一棵二叉树的深度可以使用递归算法,代码如下:
```python
def depth(node):
if node is None:
return 0
else:
left_depth = depth(node.left)
right_depth = depth(node.right)
return max(left_depth, right_depth) + 1
```
其中,如果节点为空,则深度为0;否则,递归计算左子树和右子树的深度,然后返回左右子树深度的最大值再加上1。
接下来,计算二叉树的总节点个数同样可以使用递归算法,代码如下:
```python
def count_nodes(node):
if node is None:
return 0
else:
left_count = count_nodes(node.left)
right_count = count_nodes(node.right)
return left_count + right_count + 1
```
其中,如果节点为空,则节点个数为0;否则,递归计算左子树和右子树的节点个数,然后返回左右子树节点个数之和再加上1。
最后,计算二叉树的叶子节点个数同样可以使用递归算法,代码如下:
```python
def count_leaves(node):
if node is None:
return 0
elif node.left is None and node.right is None:
return 1
else:
left_count = count_leaves(node.left)
right_count = count_leaves(node.right)
return left_count + right_count
```
其中,如果节点为空,则叶子节点个数为0;如果节点的左右子树均为空,则该节点为叶子节点,叶子节点个数为1;否则,递归计算左子树和右子树的叶子节点个数,然后返回左右子树叶子节点个数之和。
希望这些算法对你有帮助,如有疑问请随时提出。
阅读全文