-
Notifications
You must be signed in to change notification settings - Fork 77
/
validate_binary_search_tree.py
89 lines (68 loc) · 2.36 KB
/
validate_binary_search_tree.py
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
# coding: utf-8
"""
https://leetcode.com/problems/validate-binary-search-tree/
"""
import sys
class TreeNode: # pragma: no cover
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def inorder_traverse(node):
if not node:
return
yield from inorder_traverse(node.left)
yield node.val
yield from inorder_traverse(node.right)
values = list(inorder_traverse(root))
sorted_values = sorted(values)
dedup_values = set(values)
return (values == sorted_values) and (len(values) == len(dedup_values))
class Solution2:
def isValidBST(self, root: TreeNode) -> bool:
def inorder_traverse(node):
if not node:
return None
yield from inorder_traverse(node.left)
yield node.val
yield from inorder_traverse(node.right)
# last_val = float('-inf')
last_val = -sys.maxsize
for val in inorder_traverse(root):
if last_val >= val:
return False
last_val = val
# The following solution doesn't work since you cannot just check a single node at a time.
# There might be a binary tree like this which is not BST:
# 5
# / \
# 1 6
# / \
# 4 7
# def inorder_traverse(node):
# if not node:
# return
# yield from inorder_traverse(node.left)
# yield node
# yield from inorder_traverse(node.right)
# for node in inorder_traverse(root):
# if node.left:
# if node.val <= node.left.val:
# return False
# if node.right:
# if node.val >= node.right.val:
# return False
return True
class Solution3:
def isValidBST(self, root: TreeNode) -> bool:
def is_bst(node, lower=float('-inf'), upper=float('inf')):
if not node:
return True
return all([
lower < node.val < upper,
is_bst(node.left, lower, node.val),
is_bst(node.right, node.val, upper),
])
return is_bst(root)