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.

一道medium的题目，考察二叉搜索树是否合格。一种直接的思路是根据题意，判断结点左子树的值是否都小于结点的值，结点的右子树的值是否都大于结点的值。

但是这种两重判断十分麻烦，另外一种思路也是我拿到题目最先想到的，二叉搜索树在中序遍历时返回的是一个非递减序列，在本题的意思：是一个递增序列。所以只需保存中序遍历前一个结点的值,比较当前结点的值是否大于前一个结点的值。只需要稍微修改中序遍历的代码，就可以实现，先给出一个利用栈的迭代解法，时间复杂度O(n),空间复杂度O(logn),代码如下：

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        stack = []
        prev = None
        cur = root
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                if prev!=None and prev >= cur.val:
                   return False
                prev = cur.val
                cur = cur.right
        return True

第二种递归实现，其实还是中序遍历，同样需要在遍历的时候比较当前遍历到的值是否大于前一个遍历到的结点的值。所以在遍历的时候，需要一个可以比较的前序结点的值，遍历当前结点时，如果不需要结束，需要将这个前序结点的值更新为当前结点的值，之后去验证右子树是否合格。其实还是一个divide and conquer的过程。但是需要注意这题的prev一定要是引用，递归调用的函数之间可以共享这个值的改变。调用函数时传入的prev不一定是当前结点的前继，需要通过遍历子函数获得。如果不使用引用是错误的，比如在每个结点divide and conquer时，比较完该结点左子树之后，prev仍然是调用该结点时候的值(prev.parent.val)，没有反映左子树中的最大值(其实也就是某个结点调用子结点时，父结点并不一定是该子结点的直接前继，调用时传递的prev值并不是直接前继的结点值)。即时间复杂度O(n),空间复杂度为O(logn),代码如下：

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        prev = [-sys.maxint-1]
        return self.helper(root)
    def helper(self,node):
        if not node:
            return True
        if not self.helper(node.left):
            return False
        if prev[0] >= node.val:
            return False
        prev[0] = node.val
        return self.helper(node.right)