本文共 2026 字，大约阅读时间需要 6 分钟。

题目要求我们判断两个不同的插入序列是否能生成相同的二叉搜索树。解决方案是分别构建每个序列对应的二叉搜索树，并比较它们是否结构相同。

分析过程

优化步骤

最终解决方案

代码修正

修正new操作符，确保正确创建节点对象。

#include 
   
    
using namespace std;
struct node {
    int val;
    node* left;
    node* right;
    node(int x) : val(x), left(nullptr), right(nullptr) {}
};
node* build(node* tnode, int tval) {
    if (tnode == nullptr) {
        return new node(tval);
    }
    if (tval < tnode->val) {
        tnode->left = build(tnode->left, tval);
    } else {
        tnode->right = build(tnode->right, tval);
    }
    return tnode;
}
bool SameTree(node* root, node* croot) {
    if (root == nullptr && croot == nullptr) return true;
    if (root == nullptr || croot == nullptr) return false;
    if (root->val == croot->val) {
        return SameTree(root->left, croot->left) &&
               SameTree(root->right, croot->right);
    } else {
        return false;
    }
}
int main() {
    int n, l;
    while (true) {
        cin >> n;
        if (n == 0) break;
        cin >> l;
        vector
    
      init_seq(n);
        for (int i = 0; i < n; ++i) {
            cin >> init_seq[i];
        }
        node* root = nullptr;
        for (int x : init_seq) {
            root = build(root, x);
        }
        while (l--) {
            node* croot = nullptr;
            for (int x : init_seq) {
                croot = build(croot, x);
            }
            if (SameTree(root, croot)) {
                cout << "Yes";
            } else {
                cout << "No";
            }
            // 为了处理多个测试用例，清理root
            root = nullptr;
        }
    }
    return 0;
}
    
   

解决方案总结

该解决方案通过分别构建两个序列对应的二叉搜索树，并比较它们的结构，来判断是否生成了相同的树。通过递归函数进行树的构建和比较，确保了逻辑的正确性和代码的高效性。