-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathsame2.py
More file actions
106 lines (86 loc) · 3.35 KB
/
same2.py
File metadata and controls
106 lines (86 loc) · 3.35 KB
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
# Recursive method ( any traversal pre/post/in or bfs can be used )
# 1. Go through the full recursion of both the trees separately and then decide - 100 pass
"""
def preOrder(node, order):
if node:
order.append(node.val)
if node.left:
preOrder(node.left, order)
else:
order.append(None)
if node.right:
preOrder(node.right, order)
else:
order.append(None)
return order
return preOrder(p, []) == preOrder(q, [])
"""
# 2. Go through both the trees together in single iteration, as soon as there is a mismatch exit - 100 pass
"""
def traverse(node1, node2):
# one of the nodes is null
current = False
if not node1 and not node2: # both are null
current = True
elif node1 and node2: # both are not null
# Current node
if node1.val != node2.val:
current = False
else:
current = True
# Left Node
if node1.left and node2.left:
current &= traverse(node1.left, node2.left)
elif not node1.left and not node2.left:
current &= True
else:
current &= False
# Right Node
if node1.right and node2.right:
current &= traverse(node1.right, node2.right)
elif not node1.right and not node2.right:
current &= True
else:
current &= False
return current
return traverse(p, q)
"""
# Iterative Method - 100 pass
# Create 2 stacks to track the nodes in both the trees
tree1 = [p]
tree2 = [q]
# Iterate until both the nodes in trees expire together...
while tree1 and tree2:
# Current Node check
t1 = tree1.pop(0)
t2 = tree2.pop(0)
if t1 and t2:
if t1.val != t2.val:
return False
# Add left and right of both the trees
tree1.append(t1.left) if t1.left else tree1.append(None)
tree1.append(t1.right) if t1.right else tree1.append(None)
tree2.append(t2.left) if t2.left else tree2.append(None)
tree2.append(t2.right) if t2.right else tree2.append(None)
elif not t1 and not t2: # Continue if both are None
pass
else: # Fail if one of them is None
return False
# If one tree still remains then False
if tree1 or tree2:
return False
else:
return True