给定一棵满二叉树树先序遍历的输出结果,求该树中序遍历的输出结果。
时间: 2023-09-25 18:16:30 浏览: 57
对于一棵满二叉树,其中序遍历的输出结果可以通过以下步骤得到:
1. 将树先序遍历结果分为三个部分:根节点、左子树的先序遍历结果、右子树的先序遍历结果。
2. 递归处理左子树的先序遍历结果,得到该子树的中序遍历结果。
3. 递归处理右子树的先序遍历结果,得到该子树的中序遍历结果。
4. 将根节点的值插入到左子树的中序遍历结果的末尾。
5. 将右子树的中序遍历结果插入到上一步得到的结果的末尾。
6. 返回最终的中序遍历结果。
具体实现可以参考以下代码(假设输入的树先序遍历结果已经存储在一个数组 pre 中):
```
vector<int> inorder(int l, int r) {
if (l > r) return {};
if (l == r) return {pre[l]};
int mid = l + (r - l + 1) / 2;
auto left = inorder(l + 1, mid);
auto right = inorder(mid + 1, r);
left.push_back(pre[l]);
left.insert(left.end(), right.begin(), right.end());
return left;
}
```
其中,函数 inorder(l, r) 表示处理 pre[l] 到 pre[r] 这段区间的先序遍历结果,返回对应的中序遍历结果。在函数中,首先处理边界情况,即当 l > r 或者 l == r 时,直接返回对应的结果。否则,找到当前区间的中间位置 mid,然后分别递归处理左右子树的先序遍历结果,得到对应的中序遍历结果 left 和 right。将根节点的值 pre[l] 插入到 left 的末尾,然后将 right 的结果插入到 left 的末尾,最后返回 left 即可。
相关推荐
![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_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)