4-1 是否同一棵二叉搜索树

题目

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。

简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

输出格式:

对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

输入样例:

4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

输出样例:

Yes
No
No

题目分析

三种方法求解：

1. 分别构造两颗树，比较两颗树是否相同
2. 不建树的方法：（递归方法）
   根据第一个相同的输入，将两种输入序列分为左子树和右子树，比较两个对应子树是否相同。
3. 建一棵树，再判别别的序列是否与之相同。

我们选择第三种方法：
要解决的问题如下：

1. 搜索树的表示
2. 建立搜索树
3. 判别序列和数是否一致

我的答案

//
// Created by allenhsu on 2018/11/1.
// 相同的class名字是会互相引用的
// 从大到小的细分，main函数怎么写，小函数就怎么写
#include <iostream>


using namespace std;

typedef struct BinTree *Tree;
struct BinTree{
    int v;
    int flag;   // 判断是否访问
    Tree Left, Right;
};

/**
 * 根据输入序列构造树
 * @param N 序列长度 N>0
 * @return 根据序列构造的树
 */

Tree newNode(int v){
    // Tree tree;
    Tree tree = (Tree)malloc(sizeof(struct BinTree));
    tree->v = v;
    tree->Right = NULL;
    tree->Left = NULL;
    tree->flag = 0; // 这里还不清楚flag的用意
    return tree;
}


// 思考其中的重复模式，第一步是跳出递归的关键节点为null的时候，将V放进去即可
Tree insert(Tree tree, int V){
    if (!tree) tree = newNode(V);
    else{
        if (V > tree->v){
            tree->Right = insert(tree->Right, V);
        }else{
            tree->Left = insert(tree->Left, V);
        }
    }
    return tree;
}

Tree makeTree(int N){
    Tree T;
    int i, V;
    cin >> V;
    T = newNode(V); // 有了根
    for (i = 1; i < N; ++i) {
        cin >> V;
        T = insert(T,V);
    }
    return T;
}

// 判别单个序列值是否按顺序出现
// 传入的tree应该是root
int check(Tree tree, int V){
    if (tree->flag) {
        if (V < tree->v) return check(tree->Left, V);
        else if (V > tree->v) return check(tree->Right, V);
        else return 0;
    }
    else{
        if (V == tree->v){
            tree->flag = 1;
            return 1;
        }else return 0;
    }
}

// 判断序列是否为同一棵树
int Judge(Tree T, int N){
    int V, i, flag = 0; // flag 判断该序列是否读取完毕
    cin >> V;
    if (T->v != V){
        flag = 1;
    }else T->flag = 1;

    for (i = 1; i < N; ++i) {
        cin >> V;
        if ((!flag) && (!check(T, V))){
            flag = 1;
        }
    }
    if (flag) return 0;
    else return 1;
}
// 清除各个flag节点
void ResetT(Tree T){
    if(T->Left) ResetT(T->Left);
    if (T->Right) ResetT(T->Right);
    T->flag = 0;
}
// 释放空间，从下到上
void FreeTree(Tree T){
    if (T->Left) FreeTree(T->Left);
    if(T->Right) FreeTree(T->Right);
    free(T);
}

int main(){
    int N,L,i;
    Tree T;
    cin >> N;
    while(N){
        cin >> L;
        T = makeTree(N);
        for (i = 0; i < L; i++) {
            if (Judge(T, N)) cout<< "Yes" << endl;
            else cout << "No" << endl;
            ResetT(T);
        }
        FreeTree(T);
        cin >> N;
    }
    return 0;
};

本题思考

最大的启示是，做的时候，要学会化解问题，从大到小的逐渐剖析。