统计二叉树中度为1度结点个数
时间: 2023-06-10 17:08:26 浏览: 258
计算二叉树的结点个数
5星 · 资源好评率100%
在一棵二叉树中,度为1的节点有两种情况:左子树为空或右子树为空。因此,我们可以通过遍历二叉树,统计左子树为空或右子树为空的节点个数来得到度为1的节点个数。
具体实现方法可以使用递归。对于一个节点,如果其左子树为空或右子树为空,则该节点的度为1;否则,将其左子树和右子树分别递归处理,最终将所有子树的度为1的节点个数加起来即为整棵树的度为1的节点个数。
以下是一个示例的 Python 代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_degree_one_nodes(root):
if not root:
return 0
count = 0
if (not root.left and root.right) or (root.left and not root.right):
count = 1
count += count_degree_one_nodes(root.left) + count_degree_one_nodes(root.right)
return count
```
其中,`TreeNode` 表示二叉树的节点,`count_degree_one_nodes` 函数接收树的根节点作为参数,并返回度为1的节点个数。在函数中,如果当前节点的左子树为空或右子树为空,则将 `count` 计数器加1,然后递归处理其左子树和右子树,并将结果相加。最终,函数返回计数器的值,即为度为1的节点个数。
阅读全文