LeetCode: 98. Validate Binary Search Tree

题目

原题地址：https://leetcode.com/problems/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.

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

解法

中序遍历生成数组，判断数组是否有序

通过 BST 的特性可以知道，中序遍历 BST 生成的所有节点的值组成的数组会是一个从小到大不包含重复值的有序数组。通过判断生成的数组是否是不包含重复值的有序数组就可以判断是否是个有效的 BST。

中序遍历的 Python 代码类似这样:

def inorder(root):
    if root is None:
        return
    inorder(root.left)

    # print(root)

    inorder(root.right)

这个方法的 Python 代码类似下面这样:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        self.node_vals = []
        self.inorder(root)

        pre = None
        for v in self.node_vals:
            if pre is not None and v <= pre:
                return False
            pre = v

        return True

    def inorder(self, root):
        if root is None:
            return
        self.inorder(root.left)

        self.node_vals.append(root.val)

        self.inorder(root.right)

中序遍历直接判断是否是有效的 BST

上面的方法中的数组其实可以不需要生成，直接在中序遍历的过程中判断是否有序就可以实现同样的需求。

相应的 Python 代码类似下面这个:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        self.pre = None
        return self.inorder(root)

    def inorder(self, root):
        if root is None:
            return True

        if not self.inorder(root.left):
            return False

        if self.pre is not None and root.val <= self.pre.val:
            return False

        self.pre = root

        return self.inorder(root.right)

Comments