二叉树 先序遍历abdgcefh 中序遍历dbgaechf 后序遍历是什么
时间: 2023-07-12 11:20:47 浏览: 117
根据先序遍历和中序遍历构建二叉树,可以得到如下的二叉树结构:
```
a
/ \
b c
/ / \
d e f
\
g
/ \
h i
```
其中,根据先序遍历的顺序,a为根节点,b为左子树的根节点,d为左子树的左子树的根节点,g为左子树的右子树的根节点,c为右子树的根节点,e为右子树的左子树的根节点,f为右子树的右子树的根节点。根据中序遍历的顺序,d、b、g、a、e、c、h、g、i依次为二叉树各个子树的节点,因此可以确定二叉树的结构。根据后序遍历的顺序,可以得到二叉树的后序遍历结果为dgihfeca。
相关问题
二叉树先序遍历中序遍历后序遍历
二叉树的遍历方式有三种:先序遍历、中序遍历和后序遍历。其中,先序遍历是指先访问根节点,然后递归遍历左子树和右子树;中序遍历是指先递归遍历左子树,然后访问根节点,最后递归遍历右子树;后序遍历是指先递归遍历左子树和右子树,最后访问根节点。
以下是三种遍历方式的代码实现:
1. 先序遍历
```python
def pre_order(root):
if root:
print(root.val)
pre_order(root.left)
pre_order(root.right)
```
2. 中序遍历
```python
def in_order(root):
if root:
in_order(root.left)
print(root.val)
in_order(root.right)
```
3. 后序遍历
```python
def post_order(root):
if root:
post_order(root.left)
post_order(root.right)
print(root.val)
```
二叉树先序遍历和中序遍历求后序遍历的代码
以下是二叉树先序遍历和中序遍历求后序遍历的代码:
```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$ 是二叉树的节点个数。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)