LeetCode-98——验证二叉搜索树

题目

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

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

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

​ 示例：

输入:
    2
   / \
  1   3
输出: true

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

解法

​ 这道题提供三种解法

使用二叉树中序遍历的方法

​ 根据二叉搜索树的性质，可以得出二叉搜索树使用中序遍历得到的序列应该是一个升序的序列，所以我们可以利用这一性质来判断其是否为二叉搜索树

Python 代码

def isValidBST(self, root):
    inorder = self.inorder(root)
    return inorder == list(sorted(set(inorder)))

def inorder(self, root):
    if root is None:
        return []
    return self.inorder(root.left) + [root.val] + self.inorder(root.right)

只考虑当前节点的上一级

​ 另外，我们可以简化上面的方法，因为二叉搜索树实际上就是要保证，在中序遍历的顺序下，当前节点的值一定要大于前一个节点的值

Python 代码

def isValidBST(self, root):
    self.prev = None
    return self.helper(root)

def helper(self, root):
    if root is None:
        return True
    if not self.helper(root.left):
        return False
    if self.prev and self.prev.val >= root.val:
        return False
    self.prev = root
    return self.helper(root.right)

使用递归

​ 除中序遍历的方法外，我们还可以使用递归的思想，根据二叉搜索树的性质，我们只需要满足当前节点的左子树中的最大值比节点值小，右子树中的最小值比节点值大即可证明其为二叉搜索树

Java 代码

public boolean isValidBST(TreeNode root) {
    return helper(root, null, null);
}
public boolean helper(TreeNode root, Integer min, Integer max) {
    if (root == null)
        return true;
    if (min != null && root.val <= min)
        return false;
    if (max != null && root.val >= max)
        return false;
    return helper(root.left, min, root.val) && helper(root.right, root.val, max);
}