[LeetCode] 98. Validate Binary Search Tree

98. Validate Binary Search Tree

 

Medium

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.

 

Example 1:

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

Example 2:

Input: root = [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.

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -231 <= Node.val <= 231 - 1

 

---

문제 풀이

문제 접근

1. 노드의 갯수는 크지 않아서, 시간복잡도를 생각하지 않아도 된다.
2. 시간복잡도를 떠나서 이진트리관련 문제이기 때문에, 재귀 + 이진탐색으로 접근한다.
3. 재귀를 사용하지 않으려면 스택을 사용해서 푼다. 

풀이

1. 이진 트리를 이해했다면, 부모 숫자의 크기와 자식들의 숫자 크기를 비교할 수 있다.
2. 부모의 오른쪽 자식은 부모보다 숫자가 커야한다.
3. 왼쪽 자식은 부모보다 숫자가 작아야한다. 
4. 부모 자식 크기 조건 이외에, 자식의 할아버지도 참고해야한다.
5. 문제 설명에도 나와있는데 오른쪽 부분 트리는 부모보다 커야하고 왼쪽 부분 트리는 부모보다 작아야한다.
6. 예를 들어 A(조부모), B(오른쪽 부모), C(왼쪽 손자) 라고 했을때 A < C < B 가 되어야 한다.
7. 이를 위해, 탐색을 할때 경계 값을 가지고 확인을 해야한다. 
8. C까지 내려갔을때 경계는 A와 B이다. 즉 A 보다 크고 B 보다 작아야한다.
9. 오른쪽으로 탐색할때는 최소값이 A여야하고, 왼쪽으로 탐색할때는 최대값이 B여야한다. 
10. 재귀호출을 이용하여 매번 왼쪽, 오른쪽 탐색시에 최대, 최소 경계값을 수정하면서 체크하자.
11. 경계를 넘어갈 경우 False를 반환, 그게 아닐경우는 True를 반환(2 자식 모두 없을때)하자.

소스 코드

# 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:
        def rec(node, maxVal, minVal):
            if not node:
                return True
            
            if node.val >= maxVal:
                return False
            if node.val <= minVal:
                return False
            
            l = rec(node.left, node.val, minVal)
            r = rec(node.right, maxVal, node.val)
            return l and r
        
        return rec(root, inf, -inf)