【LeetCode】【数据结构】二叉树必刷OJ题

03-01 1889阅读

【LeetCode】【数据结构】二叉树必刷OJ题

👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》

🌝每一个不曾起舞的日子,都是对生命的辜负


目录

前言

【LeetCode】226.翻转二叉树

【LeetCode】100.相同的树

【LeetCode】5.对称二叉树

【LeetCode】9.另一颗树的子树


前言

在学习完二叉树的基本知识后,博主给大家带来了几道经典的二叉树OJ题,快来试试你对于递归的理解到底如何?


欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。

=========================================================================

GITEE相关代码:🌟fanfei_c的仓库🌟

=========================================================================


【LeetCode】226.翻转二叉树

原题链接:🍏226. 翻转二叉树🍏

题目:给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

【LeetCode】【数据结构】二叉树必刷OJ题

 思路:

我们把复杂问题简单化,先考虑交换左右孩子为:

root->left=right;//假设right为右孩子

root->right=left;//假设left为左孩子

如果利用递归的思想,这里right 和 left最好是翻转后的左右子树的根节点。

那么好了,left 和 right的值如何来?

我们就可以有这样的递归过程:

 struct TreeNode* left=invertTree(root->left);

 struct TreeNode* right=invertTree(root->right);

 代码实现:

//方法1
struct TreeNode* invertTree(struct TreeNode* root)
{
    if(root==NULL)
    {
        return NULL;
    }
    struct TreeNode* left=invertTree(root->left);
    struct TreeNode* right=invertTree(root->right);
    root->left=right;
    root->right=left;
    return root;
}
//方法2
struct TreeNode* invertTree(struct TreeNode* root)
{
    if(root==NULL)
    {
        return NULL;
    }
    struct TreeNode* tmp=root->right;
    root->right=root->left;
    root->left=tmp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

【LeetCode】100.相同的树

原题链接:🍏100. 相同的树🍏

题目:给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

【LeetCode】【数据结构】二叉树必刷OJ题

 思路:

以递归的思想思考

先递推到最基础的子问题:

最基础的单个节点是否相同,那么首先如果两个都为空,证明相同返回true;

如果有一个为空,另外一个不为空则不相同返回false;

如果两个节点的值不相同,则返回false;

最后回归到大问题:

如何证明两个树都相同呢?

我们可以从左子树开始依次判断,如果不同就直接返回false,只要过程中有一个函数返回false,那么会导致程序直接结束并返回false;

如果相同就继续判断右子树,如果左右子树都递推到空指针了,那么返回true。

代码实现:

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    if(p == NULL && q == NULL)
    {
        return true;
    }
    //到达这里时,证明p、q至少有一个不为空
    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);
}

【LeetCode】5.对称二叉树

原题链接:🍏101. 对称二叉树🍏

题目:给你一个二叉树的根节点 root , 检查它是否轴对称。

【LeetCode】【数据结构】二叉树必刷OJ题

思想:

大体思想其实与相同的子树相似, 只不过这次是一棵树,那么我们可以额外构建一个函数,传递两个指针参数(左右孩子指针),当作相同的子树那里的两棵树,并且比较时我们令两个指针的左孩子与右孩子比即可。

 代码实现:

bool isSymmetricTree(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 isSymmetricTree(p->left,q->right)&&isSymmetricTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root)
{
    return isSymmetricTree(root->left,root->right);
}

【LeetCode】9.另一颗树的子树

原题链接:🍏572. 另一棵树的子树🍏

题目:给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

【LeetCode】【数据结构】二叉树必刷OJ题

 思路:

根据题目,我们直到subRoot一定不为空,那么我们就需要判断root是否为空的情况,为空直接返回false即可。

什么时候开始进行判断是否为子树呢?

当root->val与subRoot->val相等时,就进入我们是否为子树的判断,这里的判断直接引用我们写的相同的子树即可。

函数返回值为bool值,我们可以采用下面的方式进行判断(逻辑与、逻辑或的结果是真/假)。

return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);

 显然中间的逻辑操作符采用 || ,因为左右子树中只要有一个是子树即可,左子树不符合还需要访问右子树,所以采用 || 。

代码实现:

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(root->val==subRoot->val)
    {
        if(isSameTree(root,subRoot))
        {
            return true;
        }
    }
    return isSubtree(root->left,subRoot)
        ||isSubtree(root->right,subRoot);
}

=========================================================================

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

========================================================================= 

VPS购买请点击我

文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。

目录[+]