二叉树先序遍历和中序遍历求后序遍历的代码
时间: 2023-09-07 19:14:54 浏览: 91
以下是二叉树先序遍历和中序遍历求后序遍历的代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
i = inorder.index(root_val)
root.left = buildTree(preorder[1:i+1], inorder[:i])
root.right = buildTree(preorder[i+1:], inorder[i+1:])
return root
def postorderTraversal(root):
if not root:
return []
res = []
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if not node:
continue
if visited:
res.append(node.val)
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return res
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
res = postorderTraversal(root)
print(res)
```
其中,`buildTree` 函数用于根据先序遍历和中序遍历构建二叉树,`postorderTraversal` 函数用于求二叉树的后序遍历。时间复杂度为 $O(n)$,空间复杂度为 $O(n)$,其中 $n$ 是二叉树的节点个数。
阅读全文