Keshawn_lu's Blog

Leetcode 572. 另一个树的子树

字数统计: 404阅读时长: 1 min
2020/05/07 Share

题目简介:

给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

1
2
3
4
5
    3
/ \
4 5
/ \
1 2

给定的树 t:

1
2
3
  4 
/ \
1 2

返回 true,因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:

给定的树 s:

1
2
3
4
5
6
7
    3
/ \
4 5
/ \
1 2
/
0

给定的树 t:

1
2
3
  4
/ \
1 2

返回 false

思路:使用dfs方法,先找到某个节点值与子树t的根节点相等,再进行遍历,若完全相等则返回true,否则继续遍历,若s中找不到和t完全相等的子树,则返回false。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:

bool dfs(TreeNode* s, TreeNode* t){

if(s == NULL && t == NULL) //遍历后节点值均相等
return true;
if(s == NULL || t == NULL) //一个树提前遍历完,两颗树不相等
return false;
if(s -> val != t -> val) //节点值不相等,两颗树不相等
return false;

//进行到这步说明两个节点相等并且没有遍历完,进行下一层节点的遍历
return dfs(s -> left, t -> left) && dfs(s ->right, t -> right);
}

bool isSubtree(TreeNode* s, TreeNode* t) {

if(s == NULL)
return false;

if(dfs(s, t))
return true;

//有一部分相等即可
return (isSubtree(s -> left, t) || isSubtree(s -> right, t));

}
};
CATALOG
  1. 1. 题目简介: