给出一棵二叉树的前序遍历 (preorder) 和中序遍历 (inorder),求它的后序遍历 (postorder)。
时间: 2024-05-02 20:23:04 浏览: 15
好的,这个问题可以通过递归的方式来解决。首先我们可以找到根据前序遍历得到的二叉树的根节点,然后在中序遍历中找到该节点的位置,然后可以得到该节点的左子树和右子树的中序遍历序列。由于前序遍历的第二个节点一定就是根的左孩子或右孩子,所以可以根据该节点在前序遍历序列中的位置,得到该节点的左子树和右子树的前序遍历序列。然后就可以递归地求解左子树和右子树的后序遍历序列,并将根节点插入到后序遍历序列的最后面,得到整个二叉树的后序遍历序列。
代码实现可以参考以下代码:
```python
def buildTree(preorder, inorder):
if not preorder:
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):
res = []
def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
res.append(node.val)
dfs(root)
return res
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = buildTree(preorder, inorder)
postorder = postorderTraversal(root)
print(postorder) # [9, 15, 7, 20, 3]
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)