统计二叉树中叶子结点数目,并输出二叉树中叶子结点数目,计算树的深度。
时间: 2024-03-23 12:41:21 浏览: 69
二叉树的叶子结点数及深度
好的,我来为你解答这个问题。
统计二叉树中叶子结点数目可以采用递归的思想,具体步骤如下:
1. 如果当前节点为空,则返回0;
2. 如果当前节点为叶子节点,则返回1;
3. 如果当前节点为非叶子节点,则递归计算左子树和右子树中叶子节点的数目,并返回它们之和。
具体实现如下:
```python
def count_leaves(root):
if not root:
return 0
if not root.left and not root.right:
return 1
left_leaves = count_leaves(root.left)
right_leaves = count_leaves(root.right)
return left_leaves + right_leaves
```
关于计算树的深度,也可以采用递归的思想,具体步骤如下:
1. 如果当前节点为空,则返回0;
2. 如果当前节点为叶子节点,则返回1;
3. 如果当前节点为非叶子节点,则递归计算左子树和右子树的深度,取最大值,并加上1。
具体实现如下:
```python
def max_depth(root):
if not root:
return 0
if not root.left and not root.right:
return 1
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return max(left_depth, right_depth) + 1
```
完成以上代码后,你就可以统计二叉树中叶子结点数目,并输出二叉树中叶子结点数目,计算树的深度了。
阅读全文