https://leetcode.com/problems/validate-binary-search-tree/
Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
Code
# 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 isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.helper(root, None, None)
def helper(self, root, min, max):
if not root:
return True
if (min is not None and root.val <= min) or (max is not None and root.val >= max):
return False
return self.helper(root.left, min, root.val) and self.helper(root.right, root.val, max)
Idea
Just check the basic rule of BST: all nodes in a node’s left subtree should be less than the node’s value. all nodes in a node’s right subtree should be larger than the node’s value.
Another Code
# 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 isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
self.prev = None
return self.inorder(root)
def inorder(self, root):
if not root:
return True
if not self.inorder(root.left):
return False
if self.prev and self.prev.val >= root.val:
return False
self.prev = root
return self.inorder(root.right)
Idea
We use another property of BST: the inorder traversal of BST should return us an ascending order of numbers. We can do inorder traversal with a variable (`prev` in our code) recording which node we visited before we are visiting the current node. Whenever we find `prev.val` is larger than the current node’s value, we report invalidity of the tree.