已知前序遍历为58236147,中序遍历为28631547求后序遍历
时间: 2023-07-24 09:41:54 浏览: 59
根据前序遍历和中序遍历的特点,我们可以得到以下信息:
- 前序遍历的第一个元素为根节点,即5;
- 中序遍历中5的左侧为左子树的节点,右侧为右子树的节点,即[2, 8, 6, 3, 1]为左子树节点,[4, 7]为右子树节点。
我们可以根据这些信息重建二叉树,然后进行后序遍历,得到后序遍历结果。
重建二叉树:
```
5
/ \
8 4
/ \ \
2 6 7
/ \
3 1
```
后序遍历结果为: 28316574。
相关问题
已知前序遍历和中序遍历,求后序遍历
已知一棵二叉树的前序遍历和中序遍历,可以通过以下步骤求出后序遍历:
1. 找到前序遍历的第一个节点,即根节点。
2. 在中序遍历中找到根节点,从而确定左子树和右子树的范围。
3. 根据左子树和右子树的范围,可以在前序遍历中确定左子树和右子树的前序遍历。
4. 对左子树和右子树分别递归进行上述步骤,直到叶子节点。
5. 最后将左子树的后序遍历、右子树的后序遍历以及根节点合并起来就是整棵树的后序遍历。
下面是一个示例:
已知前序遍历为:[1, 2, 4, 5, 3, 6, 7]
已知中序遍历为:[4, 2, 5, 1, 6, 3, 7]
首先找到前序遍历的第一个节点,即1,它是整棵树的根节点。
在中序遍历中找到1,从而确定左子树的范围为[4, 2, 5],右子树的范围为[6, 3, 7]。
根据左子树和右子树的范围,在前序遍历中可以确定左子树的前序遍历为[2, 4, 5],右子树的前序遍历为[3, 6, 7]。
对左子树和右子树分别递归进行上述步骤,最终得到左子树的后序遍历为[4, 5, 2],右子树的后序遍历为[6, 7, 3]。
最后将左子树的后序遍历、右子树的后序遍历以及根节点1合并起来就是整棵树的后序遍历:[4, 5, 2, 6, 7, 3, 1]。
已知一颗二叉树前序遍历35421,中序遍历25431后序遍历为
根据给定的前序遍历和中序遍历,我们可以重建出原始的二叉树,并进而得到后序遍历。下面是重建二叉树的步骤:
1. 前序遍历的第一个元素是根节点,即3。
2. 在中序遍历中找到根节点的位置,根据中序遍历的性质,根节点左边的元素是左子树的节点,右边的元素是右子树的节点。在这个例子中,根节点3左边有两个元素,所以左子树有两个节点,右边有两个元素,所以右子树有两个节点。
3. 根据中序遍历的结果,我们可以知道左子树的中序遍历为[2, 5],右子树的中序遍历为[4, 1]。
4. 根据左子树的节点数量,我们可以在前序遍历中找到左子树的前序遍历为[5, 2],右子树的前序遍历为[4, 1]。
5. 递归地重建左子树和右子树。
6. 最后得到的二叉树的后序遍历为[5, 2, 4, 1, 3]。
所以,给定前序遍历35421和中序遍历25431,重建二叉树后的后序遍历为52413。