medium
Question
判断一个二叉树是否为，二叉搜索树（BST)
Notes
BST的特点：
- 节点的左支树只包含值小于当前节点值的节点
- 节点的右支树只包含值大于当前节点值的节点
- 节点的左右支树都是BST
Example 1:
2
/
1 3
BT [2,1,3]是BST
Example 2:
1
/
2 3
BT [1,2,3]不是BST.
Solution
暴力的算法是比较当前节点值和左分支的每一个节点的值，右分支的每一个节点的值，对左分支和右分支做一样的处理，O(n**2) runtime, O(n) stack space。
抓住BST的特点，做一个one pass的检查就可以，根据父节点可以知道子节点的最大最小值，如果子节点不在最大最小值范围，则直接返回False
# 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.valid(root, None, None)
def valid(self, p, low, high):
if p == None:
return True
return (low == None or p.val>low) and (high == None or p.val<high) \
and self.valid(p.left,low,p.val) \
and self.valid(p.right,p.val,high)
第二种方法将tree展开成in-order list，则该list应该是一个严格增序列。
# 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.inOrderList = []
self.inOrder(root)
return self.inOrderList == sorted(self.inOrderList) and len(set(self.inOrderList)) == len(self.inOrderList)
def inOrder(self, n):
if not n:
return
self.inOrder(n.left)
self.inOrderList.append(n.val)
self.inOrder(n.right)
