输入二叉树的先序遍历序列,以#代表空树,输出该二叉树的中序遍历序列。例如,有如下二叉树,其先序序列为:ABC##DE#G##F###,输出其中序序列:CBEGDFA
时间: 2023-06-18 21:07:48 浏览: 172
可以通过递归的方式来实现先序遍历序列转换为中序遍历序列。
具体思路如下:
1. 如果当前节点为空,则返回空字符串。
2. 如果当前节点不为空,则按照先序遍历的顺序分别遍历左子树和右子树,并将左右子树的遍历结果与当前节点的值按照中序遍历的顺序拼接起来,得到中序遍历的结果。
下面是示例代码实现:
```python
def preorder_to_inorder(preorder):
if not preorder: # 如果序列为空,则返回空字符串
return ""
root = preorder[0] # 当前节点为序列的第一个值
if root == "#":
return "" # 如果当前节点为空,则返回空字符串
left = preorder_to_inorder(preorder[1:]) # 遍历左子树
right = preorder_to_inorder(preorder[1+len(left):]) # 遍历右子树
return left + root + right # 将左右子树的遍历结果与当前节点的值按照中序遍历的顺序拼接起来
```
使用示例:
```python
preorder = "ABC##DE#G##F###"
inorder = preorder_to_inorder(preorder)
print(inorder) # 输出 CBEGDFA
```
注意:这里假设输入的先序遍历序列是合法的,即没有重复的节点。如果输入的先序遍历序列不合法,例如存在重复的节点,那么上述代码可能会出现错误。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)