Tree: 98. Validate Binary Search Tree

98. Validate Binary Search Tree

 

처음 내 코드

 

# 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: Optional[TreeNode]) -> bool:
        # bfs 로 내려가면서 좌우 비교하면 될듯
        # bfs 는 큐로
        que = deque([root])

        while que:
            l = len(que)
            for i in range(l):
                node = que.popleft()
                if node.left:
                    que.append(node.left)

                    if not (node.left.val < node.val):
                        return False

                if node.right:
                    que.append(node.right)
                    print(node.right.val,  node.val)

                    if not (node.val < node.right.val):
                        return False
        return True

 

이 로직으로는 [5,4,6,null,null,3,7] 은 검사 안됨

      5
     / \
    4   6
       / \
      3   7

 

따라서, 왼쪽 자식에 나보다 큰 넘이 있는지, 또는 오른쪽 자식에 나보다 작은 넘이 있는지.. 로직으로 구현해야 함

 

https://youtu.be/s6ATEkipzow?si=wKG601UuN-39rE-V

 

# 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: Optional[TreeNode]) -> bool:
        """
        # 왼쪽 자식에 나보다 큰 넘이 있는지,
        # 오른쪽 자식 중, 나보다 작은 넘이 있는지. 확인
        # 그런데, 노드 내려갈때마다, 
        # left, right 검색 boundery 를 넘겨줘서.. 체크하는 것이 효율적
        """
        def valid(node, left, right):
            if not node:
                return True
            
            if not(node.val < right and node.val > left):
                return False

            # 둘다 True 야지 True, 하나라도 False 이면 False
            return (valid(node.left, left, node.val) and
                    valid(node.right, node.val, right))

        return valid(root, -float("inf"), float("inf"))

 

이게 마지막..

# 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: Optional[TreeNode]) -> bool:
        # 이진 탐색 트리가 valid 하려면,
        # 좌측 서브 트리 모두는 현재 노드보다 작아야 하고
        # 우측 서브 트리 모두는 현재 노드보다 커야 함

        def valid(node, low, high):
            if not node: # 노드 없으면
                return True
            
            if not (low < node.val < high): # 범위를 벗어나면
                return False
            
            # 아니면 서브트리 검사
            # 둘다 true 여야 하므로 and
            return valid(node.left, low, node.val) and valid(node.right, node.val, high) 

        return valid(root, -float("inf"), float("inf"))