1829-扩展二叉树

根据先序遍历的规律进行中序遍历和后序遍历。
能用规律遍历，主要因为叶子节点的左右节点用'.'表示，所以才有下面的规律。

先序遍历的左右子树的根节点编号规律如下：

结合两幅图，比如根节点为$2$的子树，左孩子的编号为$3$，右孩子的编号为$6$。
所以，在遍历子树的时候，把节点编号传回去，就能够确定右子树的根节点编号。
以中序遍历为例：

int dfs1(int i)
{
    if(s[i]=='.') return i; //到底了，传回当前位置
    int l_last = dfs(i+1);  //递归左子树，根节点编号为父节点编号+1
    cout<<s[i];             //中序遍历访问当前子树的根节点
    int r_last = dfs(l_last+1); //传回子树最后一个节点编号
    return r_last;          //子树最后一个节点编号传递回去
}

通过这样的规律，根节点编号，左子树根节点编号，右子树根节点编号知道后，就能进行中序遍历或后学遍历。
后序遍历写法类似，不再给出写法。这题没有采用层次遍历，所以下标可以从$0$开始。