98. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid 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.

My Answer 1: Wrong Answer (71 / 77 test cases passed.)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if root is None:
            return True
        level = 0
        queue = [root]
        dic = {}
        while queue:
            root = queue.pop(0)
            level=level+1
            if root is not None:
                print(root.val)
                if root.val in dic: # 중복 있으면 False
                    return False
                dic[root.val] = 1
                if root.left:
                    queue.append(root.left)
                    if root.left.val >= root.val:
                        return False
                if root.right:
                    queue.append(root.right)
                    if root.right.val <= root.val:
                        return False
        
        return True

1. dic 이용해서 중복된 값이 있으면 False 리턴하도록 함
2. level-order 순회를 하면서 root.left.val >= root.val 거나 root.right.val <= root.val 면 False 리턴하도록 함

트리를 세로로 반으로 쪼개서 어케 해야하나.. 했는데 모르겠음

Solution 1: Runtime: 52 ms - 25.44% / Memory Usage: 16.4 MB - 81.87%

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root: return True
        stack = [(root, -float('inf'), float('inf'))]
        while len(stack):
            node, left, right = stack.pop()
            if node.val <= left or node.val >= right: return False
            if node.left: stack.append((node.left, left, node.val))
            if node.right: stack.append((node.right, node.val, right))
        return True

반복문 이용한 방식
[root, min, max] 식으로 stack 에 넣어주는듯
반복문이 돌면서 적절한 min 값과 max 값이 정해진다

Solution 2: Runtime: 44 ms - 73.91% / Memory Usage: 16.5 MB - 31.45%

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def rec(node, left, right):
            if node:
                if node.val <= left or node.val >= right: return False
                return rec(node.left, left, node.val) and rec(node.right, node.val, right)
            return True
        return rec(root, -float('inf'), float('inf') )

같은데 재귀 이용한 방식
런타임이 더 좋다