二叉搜索数

要判断两个二叉搜索树是否一致 只需判断先序遍历是否一致!

核心代码:

树的结构

struct node
{
    int val;
    node *left, *right;
};

二叉搜索树_建树

void insert(node *&root, int x)
{
    if (root == NULL)
    {
        root = new node();
        root->val = x;
        return;
    }
    if (root->val > x)
        insert(root->left, x);
    else
        insert(root->right, x);
}

判断是否一致

bool check(node *a, node *b)
{
    //如果a树和b数都为空说明到达叶子节点之前的节点全部符合
    if (a == NULL && b == NULL)
        return true;
//某棵树为空则不一致
    if (a == NULL && b != NULL)
        return false;
    if (a != NULL && b == NULL)
        return false;
//值不一致
    if (a->val != b->val)
        return false;
        //判断左子树 右子树是否一致
    return check(a->left, b->left) && check(a->right, b->right);
}
Last modification:June 23rd, 2020 at 11:20 pm
如果觉得我的文章对你有用,请随意赞赏