已知某二叉树的先序遍历序列是c b a d e f g h,中序遍历序列是 a b e d c g f h,则其二叉树为:
时间: 2024-03-14 07:48:20 浏览: 70
根据先序遍历序列确定根节点为 c,然后在中序遍历序列中找到 c 的位置,c 左边为左子树的中序遍历序列(a b e d),右边为右子树的中序遍历序列(g f h)。接下来,根据左子树的中序遍历序列(a b e d)和左子树的先序遍历序列(b a d e)递归构建左子树,右子树同理。构建完成后,得到的二叉树如下所示:
```
c
/ \
b g
/ \ / \
a d f h
\
e
```
相关问题
已知二叉树的先序遍历序列和中序遍历序列,输出其后序遍历序列和层次序遍历序列
可以通过先序遍历序列和中序遍历序列重建二叉树,然后对重建后的二叉树进行后序遍历和层次遍历即可。
具体步骤如下:
1. 根据先序遍历序列确定根结点。
2. 在中序遍历序列中找到根结点所在位置,根结点左边的序列是左子树的中序遍历序列,右边的序列是右子树的中序遍历序列。
3. 通过左子树的中序遍历序列长度确定先序遍历序列中左子树的先序遍历序列,右子树的先序遍历序列为剩余部分。
4. 递归处理左子树和右子树,重建二叉树。
5. 对重建后的二叉树进行后序遍历和层次遍历。
下面是 Python 代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
inorderIndex = inorder.index(preorder[0])
leftInorder = inorder[:inorderIndex]
rightInorder = inorder[inorderIndex+1:]
leftPreorder = preorder[1:len(leftInorder)+1]
rightPreorder = preorder[len(leftInorder)+1:]
root.left = buildTree(leftPreorder, leftInorder)
root.right = buildTree(rightPreorder, rightInorder)
return root
def postorderTraversal(root):
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res[::-1]
def levelOrder(root):
if not root:
return []
queue = [root]
res = []
while queue:
level = []
for i in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
print(postorderTraversal(root)) # 输出后序遍历序列 [4, 5, 2, 6, 7, 3, 1]
print(levelOrder(root)) # 输出层次遍历序列 [[1], [2, 3], [4, 5, 6, 7]]
```
已知二叉树的先序遍历序列为 DAGICJBFHE 中序遍历序列为 GACIDFBHJE 则后序遍历序列为
根据二叉树的遍历序列重构二叉树,得到的二叉树如下所示:
```
D
/ \
A I
/ / \
G C J
/ \
B F
/ \
H E
```
根据后序遍历的定义,后序遍历的最后一个节点为根节点。因此,我们可以先确定根节点为 E。然后,我们可以根据中序遍历确定左子树和右子树的节点集合。具体地,E 的左侧为左子树的节点集合 {G, A, C, I, D, F, B, H},右侧为右子树的节点集合 {J}。接下来,我们可以根据左子树和右子树的节点集合递归地确定左子树和右子树的后序遍历序列。
左子树的后序遍历序列为 {G, A, C, I, F, H, B, J, E, D},右子树的后序遍历序列为 {J}。因此,二叉树的后序遍历序列为 {G, A, C, I, F, H, B, J, E, D, J}。
因此,答案为:GACIDFBHJJEED。
阅读全文