正常建树和遍历

先序遍历

void Pre(node *F){
    if(!F)return;
    cout<value;
    Pre(F->L);
    Pre(F->R);
}

代码

/**
*输入格式:ABC##DE#G##F###
**/
#include
using namespace std;
//定义链树
struct btnode
{
  char value;
  btnode *lc;
  btnode *rc;
};

//先序建树
void build(btnode *&F)
{
  char ch;
  cin>>ch;
  if(ch=='#') F=NULL;
  else {
    F=new btnode;
    F->value=ch;
    build(F->lc);
    build(F->rc);
  }
}

//中序输出
void output(btnode *F)
{
  if(F)
  {
    output(F->lc);
    cout<value;
    output(F->rc);
  }
}

int main()
{
  btnode *F;
  build(F);
  output(F);
  return 0;
}

实战

根据先序/后序+中序建树

前提：
若二叉树的节点值各不相同，则二叉树先序，中序，后序均唯一。
由先序和中序序列 或者 中序和后序序列可以确定唯一的二叉树

思想

先序和中序：先序判断根，中序判断左右
中序和后序：后序判断根，中序判断左右
一、已知二叉树的前序序列和中序序列，建树。

在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。
但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。
因此我们扫描中序遍历序列，就能找到根结点的值。

　分别找到了左、右子树的前序遍历序列和中序遍历序列，我们就可以用递归方法分别去构建左右子树。

代码步骤：
1、确定树的根节点。 树根是当前树中所有元素在前序遍历中最先出现的元素。

2、求解树的子树。
找出根节点在中序遍历中的位置，
根左边的所有元素就是左子树，根右边的所有元素就是右子树。
若根节点左边或右边为空，则该方向子树为空；
若根节点左边和右边都为空，则根节点已经为叶子节点。

3、递归求解树。 将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。

代码

#include 
using namespace std;
struct node
{
    char value;
    node *L;
    node *R;
};
char pre[58];
char pos[58];
int n;
int ans = 0;

node *buildtree(char pre[], char pos[], int n, int cnt)
{
    if (n == 0)
        return NULL;
    node *F = new node;
    char root = pre[0];
    F->value = root;
    int k = 0;
    for (int i = 0; i < n; i++)
    {
        if (pos[i] == root)
        {
            k = i;
            break;
        }
    }
    cnt++;
    F->L = buildtree(pre + 1, pos, k, cnt);
    //左子树的先序头结点为pre+1，，左子树的中序头结点为pos，左子树的长度为k，
    if (F->L)
    {
        ans = max(cnt, ans);
    }
    F->R = buildtree(pre + k + 1, pos + k + 1, n - k - 1, cnt);
    //左子树的先序头结点为pre+k+1，左子树的中序头结点为pos+k+1，左子树的长度为n-k-1，
    if (F->R)
    {
        ans = max(cnt, ans);
    }
    return F;
}
int main()
{
    cin >> n;
    cin >> pre;
    cin >> pos;
    // cout<

#include
using namespace std;

int dfs(char a[],char b[],int n){
    int i;
    if(n==0)return 0;
    for(i=0;iy?x:y;
}
int main()
{
    char a[101];
    char b[101];
    int n;
    cin>>n;
    cin>>a>>b;
    int cnt=dfs(a,b,n);
    cout<