简答题 用先序遍历扩充二叉树创建一颗二叉树,并统计其叶子节点数和节点总数。
时间: 2024-08-13 22:05:47 浏览: 54
使用先序遍历(根-左-右)来扩充二叉树并创建一棵二叉树,可以按照递归的方式进行。步骤如下:
1. **创建根节点**:根据先序遍历的第一个元素创建新的二叉树根节点。
2. **递归遍历**:对于每个子序列(即后两个元素),在当前节点的左子树或右子树中递归创建对应的子树。如果遍历到的子序列为空,则表示到达叶子节点。
3. **统计**:在遍历过程中,每遇到一个空的子序列(表示叶子节点),就将叶子节点计数加一。同时,每次递归都会增加当前节点的子节点数量,直到遍历完整个序列。
下面是具体的伪代码示例:
```python
def build_tree(preorder):
# 先序遍历的第一个元素作为根节点
if not preorder:
return None
root = TreeNode(preorder[0]) # 创建根节点
root.left = build_tree(preorder[1:]) # 递归左子树
root.right = build_tree(preorder[2:] if len(preorder) > 2 else []) # 递归右子树
def count_leaves_and_nodes(root):
if root is None:
return 0, 0 # 如果是空节点,返回叶子节点数和节点数均为0
left_leaves, left_nodes = count_leaves_and_nodes(root.left)
right_leaves, right_nodes = count_leaves_and_nodes(root.right)
leaves = left_leaves + right_leaves + (1 if root.left is None and root.right is None else 0) # 叶子节点数
nodes = left_nodes + right_nodes + 1 # 节点总数(包括根节点)
return leaves, nodes
# 示例:
preorder = [1, 2, 3, 4, 5, 6, None, None] # 假设这是一个完整的先序遍历序列
root = build_tree(preorder)
leaves, total_nodes = count_leaves_and_nodes(root)
```
阅读全文