[LeetCode] Python - 98. Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree

Validate Binary Search Tree - LeetCode

1. left 서브트리는 부모노드보다 작기때문에, 재귀함수를 통해 호출할때 right 파라미터에 현재 node의 값을 넣어 오른쪽 boundary를 갱신시켜줍니다.

2. right 서브트리는 부모노드보다 커야하기 때문에, 다음번 노드를 탐색하기위해 재귀함수로 호출할때 left 파라미터에 현재 node의 값을 넣어 왼쪽 boundary를 갱신시켜줍니다.

3. 기저조건으로 node가 없다면 true이고, 올바른 binary tree의 조건에 해당하지 않는다면 false를 리턴시켜줍니다.

 

Python Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.valid(root, float("-inf"), float("inf"))
    
    def valid(self, node, left, right):
        if not node:
            return True
        if not (node.val < right and node.val > left):
            return False
        # left 서브트리는 부모노드보다 작다. 오른쪽 boundary 갱신해줘야함 -> right자리에 node.val
        # right 서브트리는 부모노드보다 크다. 왼쪽 boundary 갱신 -> left 자리에 node.val
        return self.valid(node.left, left, node.val) and self.valid(node.right, node.val, right)