LeetCode-Solutions/Python/validate-binary-search-tree.py at master · Monika-R/LeetCode-Solutions · GitHub

History

56 lines (46 loc) · 1.48 KB

Raw

# Time: O(n)

# Space: O(1)

class TreeNode(object):

def __init__(self, x):

self.val = x

self.left = None

self.right = None

# Morris Traversal Solution

class Solution(object):

# @param root, a tree node

# @return a list of integers

def isValidBST(self, root):

prev, cur = None, root

while cur:

if cur.left is None:

if prev and prev.val >= cur.val:

return False

prev = cur

cur = cur.right

else:

node = cur.left

while node.right and node.right != cur:

node = node.right

if node.right is None:

node.right = cur

cur = cur.left

else:

if prev and prev.val >= cur.val:

return False

node.right = None

prev = cur

cur = cur.right

return True

# Time: O(n)

# Space: O(h)

class Solution2(object):

# @param root, a tree node

# @return a boolean

def isValidBST(self, root):

return self.isValidBSTRecu(root, float("-inf"), float("inf"))

def isValidBSTRecu(self, root, low, high):

if root is None:

return True

return low < root.val and root.val < high \

and self.isValidBSTRecu(root.left, low, root.val) \

and self.isValidBSTRecu(root.right, root.val, high)

LeetCode-Solutions/Python/validate-binary-search-tree.py at master · Monika-R/LeetCode-Solutions · GitHub

Expand file tree

Breadcrumbs

validate-binary-search-tree.py

Latest commit

History

Breadcrumbs

validate-binary-search-tree.py

File metadata and controls