当前位置：首页 > news >正文

L15.【LeetCode笔记】相同的树

news 2024/12/4 19:29:04

1.题目

代码模板

2.分析

通过合理的if判断分类讨论两个根节点

1.首先,p和q都为NULL的情况最好排除

2.排除了两个都为NULL的情况,剩下的情况:1.其中一个为NULL;2.两个都不为NULL

写法1

写法2

3.只剩下最后一种情况:p和q都不为NULL

3.代码

提交结果

1.题目

https://leetcode.cn/problems/same-tree/

给你两棵二叉树的根节点 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] 内
-10^4 <= Node.val <= 10^4

代码模板

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
}

2.分析

按根-->左子树-->右子树的顺序比较

分而治之的思想:根节点相同,递归比其的左子树节点和右子树节点;若两个子树的节点相同,分别递归比其的左子树节点和右子树节点......

根节点p和q有多种可能

	情况1	情况2	情况3	情况4
p	NULL	!=NULL	NULL	!=NULL
q	NULL	NULL	!=NULL	!=NULL

通过合理的if判断分类讨论两个根节点

1.首先,p和q都为NULL的情况最好排除

if (p==NULL && q==NULL)return true;

2.排除了两个都为NULL的情况,剩下的情况:1.其中一个为NULL;2.两个都不为NULL

两个都不为NULL的情况是要递归处理的,因此先排除其中一个为NULL的情况

写法1

    if (p==NULL|| q==NULL)return false;

写法2

    if ((p==NULL)+(q==NULL)==1)return false;

3.只剩下最后一种情况:p和q都不为NULL

比较p->val和q->val是否相同

注意:写成if (p->val==q->val)没有什么意义,做不了任何事,判断如果不相等则返回false,否则递归比较左右子树的节点

    if (p->val!=q->val)return false;//执行到此处,说明p->val和q->val相等return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

3.代码

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{if (p==NULL && q==NULL)return true;//若能执行到此,排除了两个都为NULL的情况,剩下的情况:1.其中一个为NULL;2.两个都不为NULLif ((p==NULL)+(q==NULL)==1)return false;//只剩下最后一种情况:p和q都不为NULLif (p->val!=q->val)return false;//执行到此处,说明p->val和q->val相等return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}