LeetCode C++ 100. Same Tree【Tree/DFS/BFS】简单
发布日期:2021-07-01 02:49:58
浏览次数:3
分类:技术文章
本文共 1725 字,大约阅读时间需要 5 分钟。
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3]Output: true
Example 2:
Input: 1 1 / \ 2 2 [1,2], [1,null,2]Output: false
Example 3:
Input: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2]Output: false
题意:给定两个二叉树,编写一个函数来检验它们是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
思路1:DFS。很简单的递归函数。
代码如下:
class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if (p == nullptr && q) return false; if (q == nullptr && p) return false; if (p == nullptr && q == nullptr) return true; if (p->val == q->val) return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); else return false; }};
思路2:BFS,用一个队列同时存储两棵树上对应的结点。这里需要存储空结点 nullptr
,原因是要保持两棵树之间结构的对应。然后每次弹出两棵树的对应结点,如果都为空,就跳过;否则如果存在且值相等,就继续同时存储两棵树上面相同位置的指针;如果一个存在而另一个不存在,或者值不同,就直接返回 false
。
代码如下:
class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { queuequ; qu.push(p); qu.push(q); while (!qu.empty()) { p = qu.front(); qu.pop(); q = qu.front(); qu.pop(); if (!p && !q) continue; // 都为空, 则跳过后面的比较 if (!p || !q) return false; if (p->val != q->val) return false; qu.push(p->left); // 同时存储两棵树上面相同位置的指针 qu.push(q->left); qu.push(p->right); qu.push(q->right); } return true; }};
转载地址:https://memcpy0.blog.csdn.net/article/details/108138963 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年05月03日 11时07分59秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
结合一道面试题 看c语言运算符的执行顺序
2019-05-03
Objective-C的内省方法介绍
2019-05-03
Objective-C 内存管理 看这个就够啦
2019-05-03
IOS开发--微信支付
2019-05-03
iOS 微信支付 实用教程
2019-05-03
UIViewController的基本概念与生命周期
2019-05-03
最新方法制作自己的cocoapods开源框架的详细步骤
2019-05-03
Getting start with OCMock in you unit test
2019-05-03
李洪强和你一起学习前端之(1)Html基础
2019-05-03
李洪强iOS经典面试题142-第三方框架及其管理
2019-05-03
李洪强经典面试题38
2019-05-03
我们必须自学
2019-05-03
iOS应用内付费(IAP)开发步骤列表
2019-05-03
iOS-TextField知多少
2019-05-03
用javascript协助导入图片
2019-05-03
白话 Ruby 与 DSL 以及在 iOS 开发中的运用
2019-05-03
获取任意线程调用栈的那些事
2019-05-03
主线程中也不绝对安全的 UI 操作
2019-05-03
深入研究 Runloop 与线程保活
2019-05-03
Swift 4迁移总结:喜忧参半,新的起点
2019-05-03