给出一棵二叉搜索树的节点数和前序遍历,求它的后序遍历,用python解决
时间: 2024-05-10 10:13:44 浏览: 68
python二叉树遍历、求深度、已知前序中序 求树 求后序 - CSDN博客1
好的,这是一个比较常见的问题,我们可以通过递归来实现。以下是Python代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder):
if not preorder: # 如果前序遍历列表为空,返回None
return None
root = TreeNode(preorder[0]) # 前序遍历的第一个节点是根节点
i = 1
while i < len(preorder) and preorder[i] < preorder[0]:
i += 1
root.left = buildTree(preorder[1:i]) # 递归构建左子树
root.right = buildTree(preorder[i:]) # 递归构建右子树
return root
def postorderTraversal(root):
if not root: # 如果根节点为空,返回空列表
return []
left = postorderTraversal(root.left) # 递归遍历左子树
right = postorderTraversal(root.right) # 递归遍历右子树
return left + right + [root.val] # 将左子树遍历结果、右子树遍历结果和根节点值拼接在一起,返回后序遍历结果
preorder = [5, 3, 2, 4, 7, 6, 8]
root = buildTree(preorder)
print(postorderTraversal(root)) # 打印二叉搜索树的后序遍历结果
```
输出结果为:[2, 4, 3, 6, 8, 7, 5]。感谢您的提问!
阅读全文