LeetCode C++ 572. Subtree of Another Tree【Tree/DFS】简单
发布日期:2021-07-01 02:52:19
浏览次数:2
分类:技术文章
本文共 1308 字,大约阅读时间需要 4 分钟。
Given two non-empty binary trees s
and t
, check whether tree t
has exactly the same structure and node values with a subtree of s
. A subtree of s
is a tree consists of a node in s and all of this node’s descendants. The tree s
could also be considered as a subtree of itself.
Example 1:
Given trees
: 3 / \ 4 5 / \ 1 2
Given tree t:
4 / \ 1 2
Return true
, because t
has the same structure and node values with a subtree of s
.
Example 2:
Given trees
: 3 / \ 4 5 / \ 1 2 / 0
Given tree t
:
4 / \ 1 2
Return false
.
题意:判断 t
是不是 s
的某个子树。要求结构相同,对应结点的值也相同。
思路:双重DFS
相当于回顾了 LeetCode 100. 相同的树
这一题。我们先序DFS遍历 s
的所有结点,对以当前结点为根的每个子树,都和 t
进行树是否相同的判断。具体代码如下:
class Solution { public: bool isSubtree(TreeNode* s, TreeNode* t) { if (s == nullptr) return false; //s遍历完了,t给定为非空树,所以返回false return isSameTree(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t); //短路运算符,有一个为真,返回真 } //LeetCode 100题 相同的树的那个函数 bool isSameTree(TreeNode *s, TreeNode *t) { if (!s && !t) return true; //两子树相同 if (!s || !t) return false; //有一个不为空 if (s->val != t->val) return false; return isSameTree(s->left, t->left) && isSameTree(s->right, t->right); }};
效率如下:
执行用时:44 ms, 在所有 C++ 提交中击败了71.61% 的用户内存消耗:28.5 MB, 在所有 C++ 提交中击败了65.21% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108809024 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年05月01日 22时54分18秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
在scrollview中双击定点放大的代码
2019-05-03
IOS 程序内部切换语言 的一种方法
2019-05-03
NData转化
2019-05-03
UIScrollView小记
2019-05-03
iPhone/iOS图片相关(读取、保存、绘制、其它相关)
2019-05-03
由pushViewController说起可能出线的各种死法
2019-05-03
IOS中Json解析的四种方法
2019-05-03
IOS管理文件和目录
2019-05-03
iOS 文件和数据管理 (可能会删除本地文件储存)
2019-05-03
Foundation框架中的NSNumber对象详解
2019-05-03
iOS7Status bar适配
2019-05-03
将UIView转成UIImage,将UIImage转成PNG/JPG
2019-05-03
iOS实现截屏 并合适保存
2019-05-03
Camera
2019-05-03
ios浅谈关于nil和 NIL区别及相关问题
2019-05-03
录音声音小
2019-05-03
ios中实现对UItextField,UITextView等输入框的字数限制
2019-05-03
BeeFramework 系列二 UISignal篇下
2019-05-03
互联网协议入门(二)
2019-05-03