algorithms/algorithms/tree/is_subtree.py at master · keon/algorithms · GitHub

Name: algorithms/algorithms/tree/is_subtree.py at master · keon/algorithms · GitHub
Rating: 4.7 (5717 reviews)
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
"""
Given two binary trees s and t, check if t is a subtree of s.
A subtree of a tree t is a tree consisting of a node in t and
all of its descendants in t.

Example 1:

Given s:

 3
 / \
 4 5
 / \
 1 2

Given t:

 4
 / \
 1 2
Return true, because t is a subtree of s.

Example 2:

Given s:

 3
 / \
 4 5
 / \
 1 2
 /
 0

Given t:

 3
 /
 4
 / \
 1 2
Return false, because even though t is part of s,
it does not contain all descendants of t.

Follow up:
What if one tree is significantly lager than the other?
"""
importcollections


defis_subtree(big, small):
flag=False
queue=collections.deque()
queue.append(big)
whilequeue:
node=queue.popleft()
ifnode.val==small.val:
flag=comp(node, small)
break
else:
queue.append(node.left)
queue.append(node.right)
returnflag


defcomp(p, q):
ifpisNoneandqisNone:
returnTrue
ifpisnotNoneandqisnotNone:
returnp.val==q.valandcomp(p.left,q.left) andcomp(p.right, q.right)
returnFalse