假设二叉树采用二叉链存储结构存储,试设计一个算法,计算一棵给定二叉树的所有单分支节点个数。
时间: 2024-04-30 14:19:22 浏览: 264
算法思路:
1. 从根节点开始递归遍历二叉树;
2. 对于每个节点,判断它是否为单分支节点;
3. 如果是单分支节点,则计数器加一;
4. 遍历完整棵二叉树后,返回计数器的值。
具体实现如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_single_branch_nodes(root):
"""
计算二叉树的所有单分支节点个数
"""
if not root:
return 0
if not root.left and not root.right:
return 0
left_single = count_single_branch_nodes(root.left)
right_single = count_single_branch_nodes(root.right)
if (root.left and not root.right) or (not root.left and root.right):
return 1 + left_single + right_single
return left_single + right_single
```
其中,`TreeNode` 是二叉树节点的定义,包含值、左右子节点。`count_single_branch_nodes` 函数即为计算单分支节点个数的算法实现,其中:
- 如果当前节点为空,则返回 0;
- 如果当前节点为叶子节点,则返回 0;
- 否则,分别递归计算左右子树中的单分支节点个数;
- 如果当前节点只有左子树或只有右子树,则当前节点为单分支节点,计数器加一,并将左右子树中的单分支节点个数加起来返回;
- 否则,返回左右子树中的单分支节点个数之和。
阅读全文