LeetCode———100——相同的树

小李很执着

发布于 2024-06-15 08:57:41

460

发布于 2024-06-15 08:57:41

文章被收录于专栏：学习笔记学习笔记

1.题目

. - 力扣（LeetCode）

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

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

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104

2.解答

首先，我们判断两个节点p和q是否都为空，如果是，则表示当前子树相同，返回true。然后，我们判断p和q是否有一个为空，如果是，则表示当前子树不相同，返回false。最后，我们判断p和q的值是否相等，如果不相等，则表示当前子树不相同，返回false。然后，我们递归判断p的左子树和q的左子树的相同性，以及p的右子树和q的右子树的相同性。最终，如果所有子树都相同，返回true，否则返回false。这种方法的时间复杂度是O(n)，其中n是两个二叉树中节点的个数。

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);
}