网站建站服务的公司,杭州专业网站制作,建筑工程网络计划电子版,视频门户网站建设方案#x1f604;#x1f60a;#x1f606;#x1f603;#x1f604;#x1f60a;#x1f606;#x1f603;
开始cpp刷题之旅。
依旧是追求耗时0s的一天。 100. 相同的树
给你两棵二叉树的根节点 p 和 q #xff0c;编写一个函数来检验这两棵树是否相同。
如果两个树在…
开始cpp刷题之旅。
依旧是追求耗时0s的一天。 100. 相同的树
给你两棵二叉树的根节点 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
思路
今天又是做一道树的题目我感觉跟树相关的题目用递归都比较好理解一点。
我看LeetCode官方的解法也是使用递归。比较好理解一点。
比较简单的思路。
如果两个二叉树都为空则两个二叉树相同。如果两个二叉树中有且只有一个为空则两个二叉树一定不相同。
如果两个二叉树都不为空那么首先判断它们的根节点的值是否相同若不相同则两个二叉树一定不同若相同再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程因此可以使用深度优先搜索递归地判断两个二叉树是否相同。
解法一
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if (p nullptr q nullptr) {return true;} else if (p nullptr || q nullptr) {return false;} else if (p-val ! q-val) {return false;} else {return isSameTree(p-left, q-left) isSameTree(p-right, q-right);}}
};看一下提交记录 官方出品必属精品perfect
解法二
依旧是基于递归 不过是一种更优雅的书写方式借鉴官方解题思路先判断是否为空再判断根节点接着再判断左右节点。
任意一环不相等就返回false全部通过后返回true优雅的写法我们可以直接这样去写。
returnab通过上述写法我们就可以将解法一的代码这样压缩。
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if(pnullptr || q nullptr) return pq;return p-valq-val isSameTree(p-left,q-left) isSameTree(p-right,q-right);}
};两行代码搞定比较简洁也挺好理解。
看一下提交记录 OKperfect
