给定一棵满二叉树树先序遍历的输出结果,求该树中序遍历的输出结果。
时间: 2024-05-15 14:17:38 浏览: 16
可以用递归的方法解决该问题。具体步骤如下:
1. 如果先序遍历得到的序列为空,则中序遍历序列也为空,直接返回。
2. 先序遍历得到的序列的第一个元素一定是根节点,将其从序列中删除,并将其作为根节点新建一个节点。
3. 找到根节点在中序遍历序列中的位置,以此将中序遍历序列分为左子树和右子树。
4. 对左子树和右子树分别递归调用求解函数,得到左子树和右子树的根节点,分别将其作为根节点的左子节点和右子节点。
5. 返回根节点。
具体实现代码如下:
```
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder):
if not preorder:
return None
root_val = preorder.pop(0)
root = Node(root_val)
i = 0
while i < len(preorder) and preorder[i] < root_val:
i += 1
root.left = build_tree(preorder[:i])
root.right = build_tree(preorder[i:])
return root
def inorder_traversal(root):
if not root:
return []
res = []
res += inorder_traversal(root.left)
res.append(root.val)
res += inorder_traversal(root.right)
return res
preorder = [5, 3, 1, 4, 7, 6, 8]
root = build_tree(preorder)
inorder = inorder_traversal(root)
print(inorder) # [1, 3, 4, 5, 6, 7, 8]
```
以上是一个简单的实现,时间复杂度为O(n log n)。
相关推荐
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)