[ 98 ] [ Recursion ] Validate Binary Search Tree

문제 설명

---

Given therootof 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 keysless thanthe node's key.
• The right subtree of a node contains only nodes with keysgreater thanthe 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. 따라서, 범위를 기준으로 Validate 진행
   • 초기 범위를 -2의 32승 ~ 2의 32승으로 두고
   • 현재 노드의 값이 범위 내에 들어있는지 검사(들어있지 않다면 False)
   • 현재 노드의 값이 범위 내에 들어있으면 자식 노드들 방문
     • 방문할 때, 범위 조절해주어야 함. 현재 범위가 (a ~ b)라면
     • 왼쪽 방문할 때는 (a ~ 현재 노드의 값)
     • 오른쪽 방문할 때는 (현재 노드의 값 ~ b)
3. 모든 노드들에 대해 조건 만족하는 경우 이진 트리이므로 True, 아니면 False 리턴

---

소스 코드

---

# 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:
        flag = False
        def validate(root, fr, to):
            if root == None:
                return True

            if fr < root.val and root.val < to:
                return validate(root.left, fr, root.val) and validate(root.right, root.val, to)
            else:
                return False

        return validate(root, -2**32, 2**32)