比较两个二叉搜索树并确定子树是否在二叉搜索树中

Question

我试图为两个问题开发一个解决方案，第一个是确定两个二叉搜索树（BST）是否相同，第二个是确定子树是否在具有所有后代节点的 BST 中。

这是我的解决方案，我得到了一些错误的结果，我不知道问题出在哪里。

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;


int compare_bst(Node* root_p, Node* root_q) {
    if (root_p && root_q) {
        if (root_p->data != root_q->data)
            return 0;
        compare_bst(root_p->left, root_q->left);
        compare_bst(root_p->right, root_q->right);
    }
    return 1;
}

int has_subtree(Node* root, Node* sub_root) {
    if (root){
        if (compare_bst(root, sub_root))
            return 1;
        has_subtree(root->left, sub_root);
        has_subtree(root->right, sub_root);
    }
    return 0;
}

Answer 1

您的代码忽略了递归调用返回的结果，因此这些调用没有任何好处。

在第一个函数中both递归调用必须返回1才能使最终结果为1。在第二个函数中either递归调用必须返回1。

此外，当一棵树是空的而另一棵树不是时，那么你不应该返回 1.

这里是更正：

int compare_bst(Node* root_p, Node* root_q) {
    if (root_p && root_q) {
        if (root_p->data != root_q->data)
            return 0;
        return compare_bst(root_p->left, root_q->left) &&
               compare_bst(root_p->right, root_q->right);
    }
    return !root_p && !root_q; // Require that both are NULL
}

int has_subtree(Node* root, Node* sub_root) {
    if (root){
        if (compare_bst(root, sub_root))
            return 1;
        return has_subtree(root->left, sub_root) ||
               has_subtree(root->right, sub_root);
    }
    return 0;
}

您可以通过将不同的条件组合成一个表达式来缩短它：

int compare_bst(Node* root_p, Node* root_q) {
    return root_p && root_q
         ? root_p->data == root_q->data && 
           compare_bst(root_p->left, root_q->left) &&
           compare_bst(root_p->right, root_q->right)
         : !root_p && !root_q;
}

int has_subtree(Node* root, Node* sub_root) {
    return !!root &&
           (   compare_bst(root, sub_root) ||
               has_subtree(root->left, sub_root) ||
               has_subtree(root->right, sub_root)
           );
}