题目练习之二叉树那些事儿

用户11352420

发布于 2024-11-07 21:41:29

580

发布于 2024-11-07 21:41:29

文章被收录于专栏：编程学习

知道了二叉树的结构和一些基本操作~这一篇博客是一些关于二叉树的OJ练习题~

练习1：单值二叉树

力扣——965单值二叉树

题目

题目中给出了单值二叉树的含义就是二叉树每一个结点保存的数据相等，函数返回值是bool类型，如果是单值二叉树就返回true，否则返回false。同时题目也给出了它定义的二叉树

思路

既然这里涉及到保存数据的比较，那么肯定需要遍历我们的二叉树了，具体怎么比较呢？我们给出思路~

思路：让根结点分别与左右孩子结点（孩子结点要不为空）数据比较~如果不相等就返回false~（这里根结点与左右孩子结点比较，就不需要左右孩子结点之间进行比较了，如果【根结点==右孩子结点】&&【根结点==右孩子结点】那么【左孩子结点==右孩子结点】处理特殊情况：如果根结点为空，return true; 依次递归比较树的左右子树

代码

bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)
    {
        return true;
    }
    //根结点分别与不为空左右孩子结点数据比较
    //不相等返回false
    if(root->left && root->val != root->left->val)
    {
        return false;
    }
    if(root->right && root->val != root->right->val)
    {
        return false;
    }
    //递归比较
    return (isUnivalTree(root->left))&&(isUnivalTree(root->right));
}

提交通过~再一次体会到了二叉树递归的魅力~

练习2：相同的树

力扣——100相同的树

题目

这个题目希望我们判断两颗树是不是相同的，二叉树相同也就是它们相对应的结点保存的数据相同~

思路

思路：这个题同样是递归比较的方法，比较两颗树相对应的结点是否相同，如果不相同就返回false 处理特殊情况：如果两个结点都为空 return true; 如果只有一个结点为空 return false；依次递归比较两颗树的左右子树

代码

bool isSameTree(struct TreeNode* p, struct 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);
}

提交通过~

练习3：另外一棵树的子树

力扣——另外一棵树的子树

题目

这里是不是就与上一个题目有相通的地方，如果判断一个树是不是另外一棵树的子树，我们是不是也就可以从根结点开始遍历另外一棵树与树进行比较判断是不是相同的树，进而判断是不是子树

思路

从根结点root开始判断，两颗树是不是相同的树，如果不是将左右子树与subRoot进行判断是不是相同的树~ 注意：当根结点为NULL，说明两棵树一定不是相同的树，那么subRoot也就不是root的子树，返回false。

代码

我们这里就可以直接把判断是不是相同的树的代码拿过来~

 bool isSameTree(struct TreeNode* p, struct 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);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if(root == NULL)
    {
        return false;
    }
    //两颗树相同是子树
    if(isSameTree(root , subRoot))
    {
        return true;
    }
    //递归遍历判断左右子树
    //只要有一个满足就是
    return (isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot));
}

提交通过~

练习4：对称二叉树

力扣——101对称二叉树

题目

这里需要我们判断是不是轴对称图形，不是判断左右子树相同，这个题应该怎么做呢？

思路

有了前面两题的基础，相信这一个题目也就是手到擒来~

思路：如果root为NULL，直接返回true。接着我们只需要判断左右子树是不是对称的树，这里的对称也就说明左子树的左结点保存的数据等于右子树的右结点保存的数据，左子树的右结点保存的数据等于右子树的左结点保存的数据。（判断一个树是否对称，首先要判断左右孩子是否对称相等，还需要判断左孩子的左子树是否和右孩子的右子树对称，左孩子的右子树是否和右孩子的左子树对称。）

代码

 bool isSameTree(struct TreeNode* p, struct 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->right) && isSameTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root) {
    if(root == NULL)
    {
        return true;
    }
    //比较左右子树
    if(isSameTree(root->left,root->right))
    {
        return true;
    }
    //else与最近的if搭配
    else
    {
        return false;
    }
}