给定一个二叉树的前序遍历字符串,当节点为 NULL 时,它的输出为 “-”。请创建一个与字符串对应的二叉树。请计算树的高度并计算树中叶节点的数量。
时间: 2024-09-30 10:12:14 浏览: 50
给定一个前序遍历字符串,例如 "ab-de-cf-gh",我们可以理解为先访问根节点 a,然后左子树 b 和 -,接着右子树 d-e,再左子树 c-f,最后右子树 g-h。每个 '-' 表示当前节点为空。
要构建这样的二叉树,我们需要按照前序遍历的顺序进行。首先找到第一个非-'字符作为根节点,然后在其后的字符串中寻找第一个非-'字符作为左孩子的前驱,直到遇到 '-';同理,找到下一个非-'字符作为右孩子的前驱,直到再次遇到 '-' 或到达字符串结尾。
对于高度计算,我们从根开始递归地计算左、右子树的最大高度加一。对于叶节点,它们没有子节点,所以前序遍历中直接跟随 '- ' 的就是叶节点。
下面是创建二叉树的一个简单步骤:
1. 将字符串切分成子串,代表左右子树的序列。
2. 根据前序规则构造二叉树节点。
3. 对于每个非空子串,递归地创建子树并连接到当前节点。
4. 遍历完成时,返回根节点以及其高度和叶节点数。
计算树的高度和叶节点数的函数可能如下:
```python
def build_tree(preorder):
def helper(i):
if i >= len(preorder) or preorder[i] == "-":
return None, 0
node = TreeNode(preorder[i])
left, l_height = helper(i + 1)
right, r_height = helper(i + 1 + l_height + int(left is not None))
node.left = left
node.right = right
return node, max(l_height, r_height) + 1
root, height = helper(0)
leaf_count = count_leaves(root)
return root, height, leaf_count
def count_leaves(node):
if node is None:
return 0
if node.left is None and node.right is None:
return 1
return count_leaves(node.left) + count_leaves(node.right)
# 使用方法:
preorder_string = "ab-de-cf-gh"
root, height, leaf_count = build_tree(preorder_string)
```
阅读全文