[Leetcode] 98. Validate Binary Search Tree

문제 바로가기

Backtracking

처음에 생각했던 풀이 방식이다.
DFS로 접근하며 각 subtree의 최대/최소 값과 parent node의 비교를 통해 True/False를 반환한다.

Time Complexity: $O(n)$
Space Complexity: $O(n)$

# 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: TreeNode, minmax: List[int] = []) -> bool:
        if not root:
            minmax.append(float("inf"))
            minmax.append(float("-inf"))
            return True
        
        leftMinMax, rightMinMax = [], []
        if not self.isValidBST(root.left, leftMinMax):
            return False
        if not self.isValidBST(root.right, rightMinMax):
            return False
        if not leftMinMax[1] < root.val < rightMinMax[0]:
            return False
        
        minmax.append(min(leftMinMax[0], root.val))
        minmax.append(max(rightMinMax[1], root.val))
        return True

DFS

말단 노드에서부터 subtree의 min/max를 축적하며 올라오는 방식이 아닌, root 노드에서부터 각 node에서 가능한 low, high 값을 비교하며 내려가 True/False를 계산하는 방식이다.
예를 들어 left child node는 parent의 값보다 작아야 하므로 high는 parent.value가 된다. low는 parent의 low를 계승한다.

Time Complexity: $O(n)$
Space Complexity: $O(n)$

# 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: TreeNode, low= float("-inf"), high= float("inf")) -> bool:
        if not root:
            return True
        if root.val <= low or root.val >= high:
            return False
        if self.isValidBST(root.left, low, root.val) and \
            self.isValidBST(root.right, root.val, high):
            return True
        return False