数据结构之二叉树基础OJ练习检查两颗树是否相同

x33g5p2x  于11个月前 转载在 其他  
字(0.8k)|赞(0)|评价(0)|浏览(148)

检查两颗树是否相同

题目来源:

检查两颗树是否相同

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

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

示例 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

解题思路:

二叉树的好多问题我们都要用到分治,分治就是大问题分成小问题,小问题再继续分,直到分割成不可分割的子问题,检查两颗二叉树是不是相同的,

判断两颗树是不是相同的树,首先判断他们的根节点,然后递归判断他们的左子树右子树是不是相同的树。

代码如下:

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
	if(p == NULL && q==NULL)
        return true;
    if(p==NULL || q==NULL)
        return false;
    
    //p和q都不为NULL
    if(p->val!=q->val)
        return false;
    return isSameTree(p->left,q->left)
        && isSameTree(p->right,q->right);
}

如果p和q都为空时,说明两颗树都为空树,返回true,,如果第一个if语句没返回说明p、q至少有一个不为空,然后如果p、q有一个为空就返回false,当p、q都不为空时,判断p、q的值相等不相等,不相等返回false,然后再递归左子树右子树,判断左子树和右子树是不是相同的树,时间复杂度为O(N),N个节点比较N次,空间复杂度:O(h)->h(高度)最坏是N,开辟栈帧是高度次,空间是可以重复利用的,栈帧调用完还给操作系统,会重复利用这块空间

相关文章