[LeetCode] 98. 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:

Input:

    2

   / \

  1   3

Output: true

Example 2:

    5

   / \

  1   4

     / \

    3   6

Output: false

Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value

             is 5 but its right child's value is 4.

我们用LeetCode questions conlusion_InOrder, PreOrder, PostOrder traversal里面inorder的思路和code, 只需要判断是否ans是升序即可.
04/20/2019 Update ： add one more solution using Divide and conquer. (add a class called returnType)
1. recursive   S: O(n)

class Solution:

    def validBST(self, root):

        def helper(root):

            if not root: return

            helper(root.left)

            ans.append(root.val)

            helper(root.right)

        ans = []

        helper(root)

        for i in range(1, len(ans)):

            if ans[i] <= ans[i-1]: return False

        return True

2. iterable S; O(n) . 因为有stack

class Solution:

    def validBST(self, root):

        stack, pre = [], None

        while stack or root:

            if root:

                stack.append(root)

                root = root.left

            else:

                node = stack.pop()

                if pre != None and node.val <= pre:

                    return False

                pre = node.val

                root = node.right

        return True

3. Divide and Conquer

class ResultType:

    def __init__(self, isBST, minVal, maxVal):

        self.isBST = isBST

        self.minVal = minVal

        self.maxVal = maxVal

class Solution:

    def validBST(self, root):

        def helper(root):

            if not root:

                return ResultType(True, float('inf'), float('-inf'))

            left = helper(root.left)

            right = helper(root.right)

            if not left.isBST or not right.isBST or (root.left and root.val <= left.maxVal) or (root.right and root.val >= right.minVal):

                return ResultType(False, 0, 0)

            return ResultType(True, min(root.val, left.minVal), max(root.val, right.maxVal))

        return helper(root).isBST

4. S: O(1)

class Solution:

    def validBST(self, root):

        ans = [None, True] # pre node, answer

        def helper(root, ans):

            if not root: return

            helper(root.left, ans)

            if ans[1] and ans[0] and ans[0].val >= root.val:

                ans[1] = False

            ans[0] = node

            helper(root.right, ans)

        helper(root, ans)

        return ans[1]

巴特西

[LeetCode] 98. Validate Binary Search Tree_Medium

最新文章

热门文章