已知二叉树前序和中序,求后序
时间: 2023-08-31 10:09:28 浏览: 113
给定二叉树前序和中序求后序
二叉树的前序遍历顺序为:根节点、左子树、右子树;中序遍历顺序为:左子树、根节点、右子树。可以利用这两个遍历顺序构建出二叉树,然后再进行后序遍历即可。
具体步骤如下:
1. 根据前序遍历找到根节点,将中序遍历分成左子树和右子树两部分。
2. 对左子树和右子树分别递归进行步骤1,直到子树只有一个节点或为空。
3. 按照左子树、右子树、根节点的顺序进行后序遍历。
下面是Python实现代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
index = inorder.index(root.val)
root.left = buildTree(preorder[1:index+1], inorder[:index])
root.right = buildTree(preorder[index+1:], inorder[index+1:])
return root
def postorderTraversal(root):
if not root:
return []
stack1 = [root]
stack2 = []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
res = []
while stack2:
res.append(stack2.pop().val)
return res
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
print(postorderTraversal(root)) # [4, 5, 2, 6, 7, 3, 1]
```
其中,buildTree函数用于构建二叉树,postorderTraversal函数用于进行后序遍历。以上代码输出[4, 5, 2, 6, 7, 3, 1],即为二叉树的后序遍历结果。
阅读全文