某二叉树的先序为ABDGHCEFI中序为DGHBAECIF画出二叉树并求后序遍历
时间: 2023-11-17 13:59:00 浏览: 25
根据引用中的思路分析,我们可以通过递归的方式构建出这棵二叉树,并求出后序遍历结果。具体步骤如下:
1. 先序遍历的第一个元素A为根节点,根据中序遍历的结果,可以将节点分为左子树和右子树两部分,即DGHBA和ECIF。
2. 对于左子树DGHBA,先序遍历为ABDGH,中序遍历为DGHBA,可以递归构建出左子树,并求出左子树的后序遍历结果为DGHB A B。
3. 对于右子树ECIF,先序遍历为CEFI,中序遍历为ECIF,可以递归构建出右子树,并求出右子树的后序遍历结果为ECIF。
4. 将左子树的后序遍历结果DGHBAB和右子树的后序遍历结果ECIF合并,得到整棵树的后序遍历结果为DGHBAECIF。
因此,这棵二叉树的后序遍历结果为DGHBAECIF。
二叉树的结构如下:
```
A
/ \
B C
/ \ / \
D G H E
/ \
F I
```
相关问题
某二叉树的先序为ABDGHCEFI中序为GDHBAECIF画出二叉树并求后序遍历
根据给出的先序和中序遍历序列,可以画出如下的二叉树:
```
A
/ \
B C
/ \ \
D E F
/
G
```
根据二叉树的后序遍历规则,我们可以得到该二叉树的后序遍历序列为:GDHGEBFICA。
--相关问题--:
1. 如何通过中序和后序遍历序列还原出原始二叉树?
2. 二叉树的遍历有哪些种类?
3.
二叉树先序遍历和中序遍历求后序遍历的代码
以下是二叉树先序遍历和中序遍历求后序遍历的代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
i = inorder.index(root_val)
root.left = buildTree(preorder[1:i+1], inorder[:i])
root.right = buildTree(preorder[i+1:], inorder[i+1:])
return root
def postorderTraversal(root):
if not root:
return []
res = []
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if not node:
continue
if visited:
res.append(node.val)
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return res
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
res = postorderTraversal(root)
print(res)
```
其中,`buildTree` 函数用于根据先序遍历和中序遍历构建二叉树,`postorderTraversal` 函数用于求二叉树的后序遍历。时间复杂度为 $O(n)$,空间复杂度为 $O(n)$,其中 $n$ 是二叉树的节点个数。