二叉树的叶子节点数目
时间: 2023-12-01 09:41:06 浏览: 65
以下是求二叉树叶子节点数目的Python代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_leaf_nodes(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)
# 示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(count_leaf_nodes(root)) # 输出:4
```
相关问题
完成二叉树的链式存储结构的表示及基本操作实现(构造二叉树、先序遍历二叉树、中 序遍历二叉树、后序遍历二叉树、测二叉树高度、统计二叉树结点数、统计二叉树叶子结点 数目)。
二叉树的链式存储结构是通过节点之间的指针来表示二叉树的结构关系。每个节点包含一个数据元素和两个指针,分别指向左子树和右子树。
下面是基本操作的实现:
1. 构造二叉树:可以通过递归的方式构造二叉树。首先创建一个根节点,然后递归地构造左子树和右子树。
2. 先序遍历二叉树:先访问根节点,然后递归地先序遍历左子树,最后递归地先序遍历右子树。
3. 中序遍历二叉树:先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。
4. 后序遍历二叉树:先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。
5. 测二叉树高度:可以通过递归的方式计算二叉树的高度。如果二叉树为空,则高度为0;否则,高度等于左子树高度和右子树高度的较大值加1。
6. 统计二叉树结点数:可以通过递归的方式统计二叉树的结点数。如果二叉树为空,则结点数为0;否则,结点数等于左子树结点数加右子树结点数再加1。
7. 统计二叉树叶子结点数目:可以通过递归的方式统计二叉树的叶子结点数目。如果二叉树为空,则叶子结点数目为0;如果二叉树只有一个结点,则叶子结点数目为1;否则,叶子结点数目等于左子树叶子结点数目加右子树叶子结点数目。
统计二叉树中叶子结点数目,并输出二叉树中叶子结点数目,计算树的深度。
好的,我来为你解答这个问题。
统计二叉树中叶子结点数目可以采用递归的思想,具体步骤如下:
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
```
完成以上代码后,你就可以统计二叉树中叶子结点数目,并输出二叉树中叶子结点数目,计算树的深度了。