先回顾一下二叉树遍历

• 前序遍历：深搜

• 中序遍历：每次从最左子树的最左下开始，顺序为左-中-右

• 后续遍历：每次从最左子树的最左下开始，顺序为左-右-中

• 层次遍历：广搜

  • 例子

  • 

  • 前序遍历:1 2 4 5 7 8 3 6
    中序遍历:4 2 7 5 8 1 3 6
    后序遍历:4 7 8 5 2 6 3 1
    层次遍历:1 2 3 4 5 6 7 8

• 在递归代码实现中，只需要调整以下3行代码实现的顺序就行了

  • 搜索（左子树），放在前就相当于先输出左子树

  • 搜索（右子树），放在前就相当于先输出右子树

  • 打印当前节点，，放在前就相当于先输出根节点

回到题目

总结为2个步骤：

• 解析字符串，建树
• 中序遍历并打印

在建树时，因为字符串是先序遍历的结果，所以我们采用先序遍历的顺序来进行树的重建，也就是

            T = new BiNode; //创建一个新节点
            T->data = ch;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild); //递归，输入先序遍历，创建出一个树。(递归！！)

及先处理本节点，再递归处理左右孩子节点。如果是其他遍历的字符串，只需要根据遍历顺序更改上述代码顺序即可。

建好树后，中序遍历就很简单了

比较关键的点，指针在定义时最好都进行NULL的初始化，不然可能存在段错误、超时等各种bug

注释写的很清楚了，完整代码如下

//根据二叉树的前序遍历字符串，构建树，并输出中序遍历结果
#include <bits/stdc++.h>
using namespace std;

string s;
int len; //每次遍历到的字符串中字符的index

//定义二叉树的节...