[LeetCode] 98. Validate Binary Search Tree 풀이 및 코드

문제

트리가 주어졌을 때, 트리가 Binary Search Tree인지 판별하라

---

코드 (Naive 버전)

트리가 BST인지를 판별하기 위해서는

1) 왼쪽 subtree, 오른쪽 subtree가 BST여야 하며, 

2) root의 왼쪽 subtree에 있는 값들은 root보다 모두 작아야 하며, root의 오른쪽 subtree에 있는 값들은 root보다 모두 커야 한다. (재귀적으로 바닥까지 모든 subtree가)

따라서 직관적으로 tree를 모두 traverse하면서 이를 확인하는 코드를 짰다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        
        #check if all its children satisfy constaint
        
        left_children = [root.left]       
        while left_children:
            for node in left_children:
                if node and node.val >= root.val:
                    return False
            left_children = [child for node in left_children if node for child in (node.left, node.right) if child]
            
        right_children = [root.right]       
        while right_children:
            for node in right_children:
                if node and node.val <= root.val:
                    return False
            right_children = [child for node in right_children if node for child in (node.left, node.right) if child]       

        return self.isValidBST(root.left) and self.isValidBST(root.right)

더 나은 방법은 없을까?

---

코드(Better Version)

재귀를 활용하는 방법도 있다. 

BST의 특성상 하위 트리로 갈수록 하위 트리가 가질 수 있는 값이 한정되게 된다. 즉 서브 트리로 갈수록 노드가 가질 수 있는 값의 범위가 줄어든다. 따라서 각 노드가 가질 수 있는 노드의 범위를 아래로 전달하면 재귀적으로 풀수 있다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
    def isValidBSTRange(self, root, range):
        if not root:
            return True
        if root.val < range[0] or root.val > range[1] or range[0] > range[1]:
            return False
        if root.left and root.left.val >= root.val:
            return False
        if root.right and root.right.val <= root.val:
            return False
            
        return self.isValidBSTRange(root.left, [range[0], root.val-1]) and self.isValidBSTRange(root.right, [root.val+1, range[1]]) 

    
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        if root.left and root.left.val >= root.val:
            return False
        if root.right and root.right.val <= root.val:
            return False
        return self.isValidBSTRange(root.left, [float('-inf'), root.val-1]) and self.isValidBSTRange(root.right, [root.val+1, float('inf')])