给出一棵二叉树的前序遍历 (preorder) 和中序遍历 (inorder),用代码实现它的后序遍历 (postorder)
时间: 2024-05-14 12:13:10 浏览: 15
好的,下面是代码实现:
```
def postorder(preorder, inorder):
if not preorder:
return []
root = preorder[0]
i = inorder.index(root)
left = postorder(preorder[1:i+1], inorder[:i])
right = postorder(preorder[i+1:], inorder[i+1:])
return left + right + [root]
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
print(postorder(preorder, inorder))
```
输出结果为:[4, 5, 2, 6, 7, 3, 1]
请问还有哪些问题需要我回答呢?
相关问题
给出一棵二叉树的前序遍历 (preorder) 和中序遍历 (inorder),求它的后序遍历 (postorder)。
好的,这个问题可以通过递归的方式来解决。首先我们可以找到根据前序遍历得到的二叉树的根节点,然后在中序遍历中找到该节点的位置,然后可以得到该节点的左子树和右子树的中序遍历序列。由于前序遍历的第二个节点一定就是根的左孩子或右孩子,所以可以根据该节点在前序遍历序列中的位置,得到该节点的左子树和右子树的前序遍历序列。然后就可以递归地求解左子树和右子树的后序遍历序列,并将根节点插入到后序遍历序列的最后面,得到整个二叉树的后序遍历序列。
代码实现可以参考以下代码:
```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]
```
给出一棵二叉树的前序遍历 和中序遍历 ,求它的后序遍历 。
假设二叉树的前序遍历为 preOrder[],中序遍历为 inOrder[],那么可以通过递归的方式求出后序遍历。
步骤如下:
1. 如果 preOrder[] 和 inOrder[] 的长度都为 0,则返回空。
2. 从 preOrder[] 中取出第一个元素,即为根节点。将该元素从 preOrder[] 中删除,并在 inOrder[] 中找到它的位置,将 inOrder[] 分成左子树和右子树两部分。
3. 对左子树进行递归,返回左子树的后序遍历序列,对右子树进行递归,返回右子树的后序遍历序列。
4. 将根节点加入左子树的后序遍历序列和右子树的后序遍历序列的末尾。
5. 返回左子树和右子树的后序遍历序列的拼接结果。
Python 代码实现如下:
```python
def postOrder(preOrder, inOrder):
if not preOrder or not inOrder:
return []
rootVal = preOrder[0]
rootIndex = inOrder.index(rootVal)
leftInOrder = inOrder[:rootIndex]
rightInOrder = inOrder[rootIndex+1:]
leftPreOrder = preOrder[1:1+len(leftInOrder)]
rightPreOrder = preOrder[1+len(leftInOrder):]
leftPostOrder = postOrder(leftPreOrder, leftInOrder)
rightPostOrder = postOrder(rightPreOrder, rightInOrder)
return leftPostOrder + rightPostOrder + [rootVal]
```
例如,对于如下二叉树:
```
1
/ \
2 3
/ \
4 5
```
前序遍历为 [1, 2, 3, 4, 5],中序遍历为 [2, 1, 4, 3, 5],则后序遍历为 [2, 4, 5, 3, 1]。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)