二叉树OJ题之三

哈喽伙伴们,有一段时间没更新博客了,主要是这段时间要准备学校的期末考试,所以没有把部分时间分给博客,今天我们一起去接着看二叉树递归有关的OJ题,今天我们要学习的是 判断相同的树,力扣题目--100    ,直达链接 https://leetcode.cn/problems/same-tree/

我们先看这道题的题目要求,给我们两棵树的根节点p,q,让我们判断两棵树是否相同,无非就是判断两棵树相应的根节点是否相等,那我们就可以开始入手做题。首先我们要先判断两棵树同时为空的情况,那就返回true即

if(p==NULL&&q==NULL)//两棵树同时为空
    {
        return true;
    }

两棵树都为空的情况判断了,还有一棵树为空,一棵树不为空的情况呢?,还是一样的套路,即

 if(p==NULL||q==NULL)//只有一颗树为空
    {
        return false;
    }

为什么这么写大家明白吗?代码能进到这个if里面前提是两棵树不能同时为空了,所以我们用||就可以判断有一棵树为空的情况,如果如果p==NULL就不会判断后面q==NULL,如果p!=NULL,会进行判断q==NULL,只要是满足二者中的一种情况,那这两棵树就不会相等,就会返回false。

树为空的情况判断了,代码继续往下走就是不是空树,那就直接判断p和q的val是否相等,即

if(p->val!=q->val)//判断p和q的val
    {
        return false;
    }

如果p和q的val不相等的话,那这两棵树注定是不相同的,无需往下继续走,直接就可以返回false。

再往下走的话就证明p和q作为两棵树的根结点是相等的,我们可以递归判断两棵树的左子树和右子树,即

return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);//递归判断左右子树

代码到这里就写完了,我们运行提交

 完整代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
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);
}

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>