设计算法求二叉树所包含的叶结点的数目并求二叉树的深度。并给出设计思想
时间: 2024-06-13 21:06:34 浏览: 11
以下是求解二叉树叶结点数目和深度的算法及设计思想:
1.算法思想:
- 对于二叉树的叶结点数目,可以通过递归的方式来实现。具体而言,对于每个节点,如果它是叶结点,则将计数器加1;否则,递归遍历它的左右子树,将左右子树的叶结点数目相加即可。
- 对于二叉树的深度,同样可以通过递归的方式来实现。具体而言,对于每个节点,如果它是叶结点,则返回0;否则,递归遍历它的左右子树,将左右子树的深度较大值加1即可。
2.算法实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_leaves(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaves(root.left) + count_leaves(root.right)
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return max(left_depth, right_depth) + 1
```
3.相关问题:
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)