给出一棵二叉搜索树的前序遍历,求它的后序遍历,用python解决
时间: 2024-01-26 08:44:45 浏览: 69
二叉树 根据前序中序求后序遍历
好的,这是一个经典的问题,可以使用递归的方式来解决。以下是Python的代码实现:
``` python
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
def construct_tree(preorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
i = 1
while i < len(preorder) and preorder[i] < root_val:
i += 1
root.left = construct_tree(preorder[1:i])
root.right = construct_tree(preorder[i:])
return root
def post_order(root):
if not root:
return []
left = post_order(root.left)
right = post_order(root.right)
return left + right + [root.val]
if __name__ == '__main__':
preorder = [5,3,2,4,7,6,8]
root = construct_tree(preorder)
print(post_order(root))
```
在这个例子中,我们使用TreeNode类来表示树节点。construct_tree函数使用二叉搜索树的性质,将前序遍历的第一个元素作为根节点,并将数组分成左右两个部分。然后递归地构建左右子树。最后,我们使用post_order函数来得到树的后序遍历。
输出为:[2, 4, 3, 6, 8, 7, 5],表示二叉搜索树的后序遍历为2 4 3 6 8 7 5。
阅读全文