Subtree of Another Tree
判断是否存在子树
my solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if (!t) return !s;
return findRoot(s, t);
}
bool findRoot(TreeNode *s, TreeNode *t) {
if (!s) return false;
if (s->val == t->val && isMatch(s, t)) return true;
return findRoot(s->left, t) || findRoot(s->right, t);
}
bool isMatch(TreeNode *s, TreeNode *t) {
if (!t) return !s;
if (!s) return false;
if (s->val != t->val) return false;
return isMatch(s->left, t->left) && isMatch(s->right, t->right);
}
};
|
简单解释的话, 就是 “归归” 算法 😂. 递归套递归, 尽管我十分不情愿. 但是因为这不是个 bst 的缘故. 只有在递归中去判断(这个判断也需要递归)才比较高效, 不然如何判断”是否存在其他节点的值和这个节点相等, 也能进行判断”就会成为一个比较费力的问题. 写出 “归归” 就像🐮被挤出了最后一滴一样不情愿😭.
the best solution
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
bool eq(TreeNode* s, TreeNode* t){
if (!s && !t) return true;
if (!s || !t) return false;
return s->val == t->val && eq(s->left, t->left)
&& eq(s->right, t->right);
}
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
return s && (eq(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t));
}
};
|
哈哈哈, 老哥你也是 “归归” 啊.
咳咳, 不过比我少了一个函数, 仔细看看.
if (!t) return !s;
if (!s) return false;
// ---------------------
if (!s && !t) return true;
if (!s || !t) return false;
就这两个表达式的处理而言, 老夫觉得自己要胜一筹! 第一个表达式就是如果 t 为假, 那么 s 为 true 则 false, 反之亦可.
而第二个表达式可以基于第一个表达式, 这时候 t 已经不可能为 false 了. 如果 s 为真, 直接返回 false 就好.