1class Solution:
2 def testIfThreeBSTNodesAreOrdered(self, node1, node2, middle):
3 # return self.bruteForce(node1, node2, middle)
4 return self.interleavingSearch(node1, node2, middle)
5
6 def bruteForce(self, node1, node2, middle):
7 self.secondNodeFound = False
8 self.middleFound = False
9 if (node1 == node2) or (node1 == middle) or (node2 == middle): return False
10
11 def dfsMiddle(node):
12 if not self.secondNodeFound and node == node2: return False
13 if node == middle:
14 self.middleFound = True
15 return True
16 if node.left: return dfsMiddle(node.left)
17 if node.right: return dfsMiddle(node.right)
18 if not dfsMiddle(node1) or not self.middleFound: return False
19
20 def dfsSecondNode(node):
21 if node == node2:
22 self.secondNodeFound = True
23 return True
24 if node.left: return dfsSecondNode(node.left)
25 if node.right: return dfsSecondNode(node.right)
26 if not dfsSecondNode(middle) or not self.secondNodeFound: return False
27 return True
28
29 def interleavingSearch(self, node1, node2, middle):
30 n1, n2 = node1, node2
31 while (n1 != node2 and n1 != middle) and (n2 != node1 and n2 != middle) and n1 and n2:
32 if n1 and n1.val > middle.val: n1 = n1.left
33 elif n1 and n1.val < middle.val: n1 = n1.right
34
35 if n2 and n2.val > middle.val: n2 = n2.left
36 elif n2 and n2.val < middle.val: n2 = n2.right
37 if (n1 != middle and n2 != middle) or (n1 == node2) or (n2 == node1): return False
38
39 target = n2 if n1 == middle else n1
40
41 def dfs(node, target):
42 if node.val > target.val: node = node.left
43 elif node.val < target.val: node = node.right
44 if node == target: return True
45
46 return dfs(middle, target)