做网站赚钱一般做什么,怎么在网站后台做标题的超链接,珠海哪个公司做网站好,中国服装设计公司排名题目一 相同的树
给你两棵二叉树的根节点 p 和 q #xff0c;编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同#xff0c;并且节点具有相同的值#xff0c;则认为它们是相同的。 首先我们要来判断下它们的根是否相等
根相等的话是否它们的左子树相等
是否…题目一 相同的树
给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 首先我们要来判断下它们的根是否相等
根相等的话是否它们的左子树相等
是否它们的右子树相等
一直到子树为空为止
大家仔细思考下这个思路对不对
接下来我们开始敲代码
首先我们想极端一点的情况
如果这个俩空指针
说明这里肯定不用判断了 返回ture就行
如果说有一个空指针 一个不为空指针的话 那么肯定是不相同的返回假就可以
接下来如果值相等 我们能判断它们相同嘛 显然不可以
所以说我们这里直接上两个不同 返回假
之后我们再判断它的左子树右子树
整体代码如下
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(pNULLqNULL){return true;}//一方为空if(pNULL||qNULL){return false;}//都不为空if(p-val!q-val){return false;}return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
}
测试一下 可以运行
题目二 对称二叉树
这里和前面相同的数的思路差不多
都是判断极值条件
我们可以借用一下前面的代码稍微修改一下将左右子树比较
之后递归展开 这里直接上代码 代码中会写明解题思路 bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(pNULLqNULL){return true;}//一方为空if(pNULL||qNULL){return false;}//都不为空if(p-val!q-val){return false;}return isSameTree(p-left,q-right)isSameTree(p-right,q-left);
}
bool isSymmetric(struct TreeNode* root) {if(rootNULL){return true;}return isSameTree(root-left,root-right);
}
这里我们要注意的是 要转换成两个子树问题才可以做
而子树问题需要再创建一个递归函数 可能是这一题的难点之一
还有一个难点就是要观察结构、
题目三 另一个树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
来源力扣LeetCode 链接https://leetcode.cn/problems/subtree-of-another-tree 我们这里只需要遍历一遍root 并且将root中的每一个节点和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(rootNULL){return false;}if(isSameTree(root,subRoot)){return true;}return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);
} 以上便是本文所有内容如有错误请各位大佬不吝赐教感谢留言
