按先序次序建立一棵二叉树,输入时,以井号表示空指针。对其进行后序遍历,并统计叶子结点的个数。
时间: 2024-04-30 21:17:35 浏览: 75
二叉树的指定结点路径
假设输入的先序遍历序列为:AB##C##,其中A是根节点,B是左子树的根节点,C是右子树的根节点,#代表空节点。
我们可以用递归的方式进行后序遍历,先遍历左子树,再遍历右子树,最后遍历根节点。统计叶子节点的个数也可以在遍历的过程中完成。
具体实现代码如下:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder):
if not preorder:
return None
val = preorder.pop(0)
if val == '#':
return None
node = Node(val)
node.left = build_tree(preorder)
node.right = build_tree(preorder)
return node
def postorder_traversal(root):
if not root:
return 0
left = postorder_traversal(root.left)
right = postorder_traversal(root.right)
if not root.left and not root.right:
return left + right + 1
return left + right
preorder = ['A', 'B', '#', '#', 'C', '#', '#']
root = build_tree(preorder)
leaf_num = postorder_traversal(root)
print(leaf_num) # 输出2,即叶子节点的个数
```
在上面的代码中,`build_tree`函数用于构建二叉树,`postorder_traversal`函数用于进行后序遍历并统计叶子节点的个数。我们可以将先序遍历序列作为参数传入`build_tree`函数中,得到构建好的二叉树。然后将该二叉树作为参数传入`postorder_traversal`函数中,得到叶子节点的个数。最后输出结果即可。
阅读全文