输入二叉树的先序遍历序列,以#代表空树,输出该二叉树的中序遍历序列。例如,有如下二叉树,其先序序列为:ABC##DE#G##F###,输出其中序序列:CBEGDFA
时间: 2023-07-24 16:12:40 浏览: 97
根据二叉树的遍历特点,先序遍历序列的第一个节点为二叉树的根节点,后面的节点分别为左子树和右子树的先序遍历序列。而中序遍历序列中,根节点的左边为左子树的中序遍历序列,右边为右子树的中序遍历序列。
因此,我们可以先根据先序遍历序列构建二叉树,然后对该二叉树进行中序遍历,即可得到中序遍历序列。
下面是Python的实现代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder):
if not preorder:
return None
val = preorder.pop(0)
if val == '#':
return None
root = TreeNode(val)
root.left = buildTree(preorder)
root.right = buildTree(preorder)
return root
def inorderTraversal(root):
if not root:
return []
res = []
res.extend(inorderTraversal(root.left))
res.append(root.val)
res.extend(inorderTraversal(root.right))
return res
preorder = 'ABC##DE#G##F###'
root = buildTree(list(preorder))
inorder = inorderTraversal(root)
print(''.join(inorder))
```
输出结果为:CBEGDFA
阅读全文