已知一个二分检索树的后序遍历序列,写出这个二分检索树,比如输出其先序序列
时间: 2023-08-10 21:24:20 浏览: 44
二叉搜索树的后序遍历序列的最后一个节点是根节点,根据二叉搜索树的性质,比根节点小的元素都在左子树,比根节点大的元素都在右子树,因此可以根据这个性质构建二叉搜索树。
具体构建过程如下:
1. 取后序遍历序列的最后一个元素作为根节点。
2. 在后序遍历序列中,从左往右找到第一个比根节点小的元素,它之前的所有元素都是左子树节点,之后的所有元素都是右子树节点。
3. 将左子树的后序遍历序列和右子树的后序遍历序列分别递归构建左子树和右子树。
构建完成后,可以通过二叉树的先序遍历来输出二叉搜索树。先访问根节点,然后递归访问左子树和右子树。
以下是示例 Python 代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(postorder):
if not postorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
idx = 0
while idx < len(postorder) - 1 and postorder[idx] < root_val:
idx += 1
root.left = build_tree(postorder[:idx])
root.right = build_tree(postorder[idx:-1])
return root
def preorder_traversal(root):
if not root:
return []
res = [root.val]
res += preorder_traversal(root.left)
res += preorder_traversal(root.right)
return res
# 示例
postorder = [1, 3, 2, 5, 7, 6, 4]
root = build_tree(postorder)
preorder = preorder_traversal(root)
print(preorder) # [4, 2, 1, 3, 6, 5, 7]
```
注意:这里假设二叉搜索树中不存在重复元素。