c++检查两个二进制搜索树是否相同

二叉搜索树的概念

二叉搜索树(Binary Search Tree，简称BST)是一个二叉树，其中每个节点都只包含一个键值，且左子树中每个节点的键值都比父节点的键值小，右子树中每个节点的键值都比父节点的键值大。BST常用于实现数据的排序和查找功能，其中查找时间复杂度为O(log n)。

两个二叉搜索树的比较

当给定两个二叉搜索树时，如果它们具有相同的结构，并且每个节点的键值也相同，则我们称这两棵树相同。判断两个BST是否相同可以采用递归的方式实现，具体实现过程如下：

步骤一：判断两个根节点是否相同

首先比较两个根节点，如果它们的键值相等，则继续比较它们的左右子树的结构和键值是否相同；否则，这两棵树就不同，直接返回False。

bool isSameTree(TreeNode* p, TreeNode* q) {
    if(p == NULL && q == NULL) { // 如果两个根节点都为空，则它们相同
        return true;
    }
    if(p == NULL || q == NULL) { // 如果其中一个根节点为空，一个非空，则它们不同
        return false;
    }
    if(p->val != q->val) { // 如果两个根节点的键值不相等，则它们不同
        return false;
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); // 递归比较左右子树结构和键值是否相同
}

步骤二：举例说明函数的执行过程

假设给定的两个BST如下：

Tree 1            Tree 2
    1                  1
   / \                / \
  2   3              2   3
 / \                / \
4   5              4   5

我们以Tree 1和Tree 2的根节点作为参数分别调用isSameTree函数，对于Tree 1和Tree 2的根节点1，它们的键值相等，因此继续比较它们的左右子树结构和键值是否相同，而对于左子树和右子树，递归调用isSameTree函数时都同样满足上述条件，因此它们也是相同的BST，最终返回True。

步骤三：时间复杂度和空间复杂度

判断两个BST是否相同的时间复杂度为O(n)，其中n为两个BST中节点的总数。空间复杂度为O(h)，其中h为两个BST中高度的最大值，因为函数的递归调用需要使用O(h)的栈空间。

步骤四：特殊情况

当给定的两个BST中存在重复的键值时，以上算法可能会判断它们相同，因为判断两个节点相同的条件只是它们的键值相等。因此，我们需要修改isSameTree函数，当判断两个节点相同时，除了它们的键值相等外，还需要判断它们的左右子树结构和键值是否相同。修改后的代码如下：

bool isSameTree(TreeNode* p, TreeNode* q) {
    if(p == NULL && q == NULL) { // 如果两个根节点都为空，则它们相同
        return true;
    }
    if(p == NULL || q == NULL) { // 如果其中一个根节点为空，一个非空，则它们不同
        return false;
    }
    if(p->val != q->val) { // 如果两个根节点的键值不相等，则它们不同
        return false;
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right); // 递归比较左右子树结构和键值是否相同
}

总结

在本文中，我们讨论了如何判断两个二叉搜索树是否相同。判断两个BST是否相同可以采用递归的方式实现，具体实现过程包括判断两个根节点是否相等，以及对它们的左右子树结构和键值递归地进行比较。当给定的两个BST中存在重复的键值时，我们需要修改原有算法，增加对节点左右子树结构和键值的判断。最终，我们得到了一个时间复杂度为O(n)，空间复杂度为O(h)的判断两个BST是否相同的算法。