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"))

 

# 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:
        # 왼쪽 값 < 현재 값, 현재 값 < 오른쪽 값 => 모든 서브 트리도 마찬가지
        # 노드는 1개 이상이어서, None 일리는 없음

        def valid(node, low, high):
            if not node:
                return True

            if not (low < node.val < high): # 기본 조건에 안맞으면
                return False

            # 현재 노드에서 기본조건은 맞으니, 이제, 서브 노드에서도 맞는지 확인
            # 왼쪽 조건, 오른쪽 조건 둘다 참이어야 해서, and 연산
            return valid(node.left, low, node.val) and valid(node.right, node.val, high)

        return valid(root, -2**31-1, 2**31)
        # return valid(root, -float("inf"), float("inf"))

 

🆚 그럼 float('-inf')랑은 어떤 차이?

• -2**31-1 은 정수형 최소값 기준이라 LeetCode 기준에 적합하고,
• float('-inf') 는 일반적인 수학적 무한대 표현이라 범용성이 더 높습니다.

둘 다 정답이지만,

상황추천	표현
LeetCode 문제에서 범위가 명시된 경우	-2**31-1, 2**31
일반 코드 or 인터뷰에서	float('-inf'), float('inf')

---

✅ 결론

• return valid(root, -2**31-1, 2**31) → 맞습니다!
• 다만 범용성과 코드의 명확성을 생각하면
  float('-inf'), float('inf') 도 고려해볼 만합니다. 😄

if not node: return True 이거는 왜 있어야 하고. 왜 True 야?

🔍 코드 분석

if not node:
    return True

이 조건은 "현재 노드가 None이면 이 서브트리는 유효한 BST이다" 라는 의미예요.

---

✅ 왜 있어야 하나요?

재귀적으로 왼쪽 / 오른쪽 자식을 계속 검사하다 보면,
리프 노드의 자식 노드까지 가게 되는데,
이 자식은 항상 None입니다.

예를 들어, 아래 트리를 보세요:

 

   2
  / \
 1   3

• 노드 1의 왼쪽과 오른쪽 자식은 None
• 이때, valid(node=None, low=..., high=...) 을 호출하게 됩니다.

그래서 이 경우는 더 이상 검사할 필요가 없고,
"아무것도 없으면 (None이면) 잘못된 건 아니다" → 즉 True 를 반환하는 거예요.

---

✅ 왜 return True 여야 하나요?

빈 서브트리는 항상 유효한 BST이기 때문입니다.

• 아무 노드도 없는 서브트리는 BST 조건을 위배하지 않음
• 따라서 "유효하다(True)"고 보는 것이 옳아요

---

📌 요약

질문	답변
왜 if not node: 있어야 해?	리프 노드의 자식(None)까지 내려갔을 때 재귀를 멈추기 위해 필요
왜 return True야?	빈 서브트리는 항상 유효한 BST이기 때문