没睡着，来做题。
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.Example 1:
2 / \ 1 3 Binary tree [2,1,3] , return true.
Example 2:
1 / \ 2 3 Binary tree [1,2,3] , return 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 getMaxVal(self, node): while node.right: node = node.right return node.val def getMinVal(self,node): while node.left: node = node.left return node.val def isValidBST(self, root): """ :type root: TreeNode :rtype: bool """ if root is None: return True if (root.left is not None) and (root.right is not None): # max Val in left subtree and min val in right subtree maxVal = self.getMaxVal(root.left) minVal = self.getMinVal(root.right) if root.val > maxVal and root.val < minVal: return self.isValidBST(root.left) and self.isValidBST(root.right) else: return False elif root.left is not None: # max val in left subtree maxVal = self.getMaxVal(root.left) if maxVal < root.val: return self.isValidBST(root.left) else: return False elif root.right is not None: # min val in right subtree minVal = self.getMinVal(root.right) if minVal > root.val: return self.isValidBST(root.right) else: return False else: return True
