给出一种不建树版本
不过不知道为何过不了测试点1:最大N,多组合
还请各位帮忙解答一下。
题目:
结果:
#include#include using namespace std; // 对于输入的各种插入序列 确定是否可生成一样的二叉搜索树 // 有三种方法 // 1.分别建两棵树判别 // 2.不建树判别 // 3.建一棵树 判别其他序列是否与该树一致 // 本方案选择不建树 嘿嘿 vector ReadIn(int N); bool Judge(vector & V1, vector & V2, int V1_left, int V1_right, int V2_left, int V2_right); int resort(vector & V, int& base); int main() { vector base_V,Test_V; int N ,L; cin >> N; while (N) { cin >> L; base_V = ReadIn(N); while(L--) { Test_V = ReadIn(N); if(Judge(base_V,Test_V,0,N-1,0,N-1)) cout <<"Yesn"; else cout << "Non"; } cin >> N; } return 0; } bool Judge(vector & V1, vector & V2, int V1_left, int V1_right, int V2_left, int V2_right) { if((V1_right == (V1_left-1)) && (V2_right == (V2_left-1))) { return true; } if((V1_right - V1_left) != (V2_right - V2_left)) return false; int V1_root = V1[V1_left]; int V2_root = V2[V2_left]; if (V1_root != V2_root) { return false; } int base_v1 = resort(V1,V1_root); int base_v2 = resort(V2,V2_root); return Judge(V1,V2,0,base_v1-1,0,base_v2-1) &&Judge(V1,V2,base_v1+1,V1_right,base_v2+1,V2_right); } vector ReadIn(int N) { int tmp = -1; vector V; while (N--) { cin >> tmp; V.push_back(tmp); } return V; } // 将数组重新排列 返回base在新数组中的位置 int resort(vector & V, int& base) { int n = V.size(); int tmp; vector V_left; vector V_right; int result = 0; // base在新数组中的索引 for(int i = 0; i < n; i++) { // cout << "&&"< base) { V_right.push_back(V[i]); } } int left_size = V_left.size(); int right_size = V_right.size(); V.clear(); for(int i = 0; i < left_size; i++) { V.push_back(V_left[i]); } result = V.size(); V.push_back(base); for(int j = 0; j < right_size; j++) { V.push_back(V_right[j]); } return result; }



