leetcode 98 验证二叉搜索树

题目如下

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
    2
   / 
  1   3
输出: true
示例 2:

输入:
    5
   / 
  1   4
     / 
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

题解

1. 直接使用二叉树的中序遍历获取一个数组，查看该数组是否为严格递增
   代码如下

# 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
        """
        ansList = self.helper(root)
        for i in range(len(ansList)-1):
            if (ansList[i] >= ansList[i+1]):
                return False
        return True

    def helper(self, root):
        if root == None:
            return []
        else:
            return self.helper(root.left) + [root.val] + self.helper(root.right)

2. 采用递归加上最大值最小值思想，当查看右节点时，最小值为该节点的值，若右节点的值比本节点的值还要小；或者查看左节点时，最大值为该节点的值，若左节点的值大于本节点的最大值。这样两种情况会返回false，
   代码如下

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean helper(TreeNode root, Long min, Long max) {
        if (root == null) {
            return true;
        } 
        if ((root.val <= min) || (root.val >= max)) {
            return false;
        }
        return helper(root.left, min, (long) root.val) && helper(root.right, (long) root.val, max);
    }
}