编写数据结构算法,在以二叉链表存储的二叉树中,求度为 2的结点的个数。
时间: 2023-12-03 10:47:39 浏览: 175
设二叉树采用链式存储结构,试设计一个算法计算一颗给定二叉树叶子节点的数目
5星 · 资源好评率100%
可以通过递归地遍历二叉树,统计度为2的节点个数。具体实现如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_degree_two_nodes(root):
if not root:
return 0
count = 0
if root.left and root.right: # 如果该节点的左右子树均存在,则度数为2
count += 1
count += count_degree_two_nodes(root.left) # 递归遍历左子树
count += count_degree_two_nodes(root.right) # 递归遍历右子树
return count
```
其中,`TreeNode` 是二叉树节点的定义,`count_degree_two_nodes` 是统计度为2的节点个数的函数。对于当前节点,如果它的左右子树均存在,则它的度数为2;然后递归遍历左右子树,将它们的度数为2的节点个数加起来返回即可。
阅读全文