[Leetcode/Python] Validate Binary Search Tree

Top Interview Questions 의 Easy Collection에 있는 문제입니다.

https://leetcode.com/explore/interview/card/top-interview-questions-easy/

 

 

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

 

Code:

# 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], floor=float('-inf'), ceiling=float('inf')) -> bool:
        if not root: 
            return True
        if root.val <= floor or root.val >= ceiling:
            return False
        # 왼쪽 탐색 시, 최댓값을 root.val로 설정, 오른쪽 탐색 시, 최솟값을 root.val로 설정
        # 이 설정이 없으면 탐색중인 작은 트리 안에서는 true일지 몰라도, 전체 트리에서는 false가 나옴
        return self.isValidBST(root.left, floor, root.val) and self.isValidBST(root.right, root.val, ceiling)

 

처음에 pass가 안된 것은 트리를 작게 보고, 현재 보고 있는 하나의 트리가 성립하는지만 판단하느라, 오류가 발생했다.

따라서 위의 코드처럼 전체의 트리를 고려하여, 짜야한다.

 

예를 들어  [5, 4, 6, null, null, 3, 7] 을 보면, 6의 왼쪽 노드가 3, 오른쪽 노드가 7로 트리가 성립한다고 판단할 수 있다.

하지만 6의 왼쪽 노드는 6보다 작으면서도 루트노드인 5의 오른쪽 트리 안에 있는 노드이므로 5보다는 커야한다.

그런데 3은 5보다도 작으므로 트리는 성립하지 않음을 알 수 있다.

 

이런 부분을 판단하려면 코드의 맨 밑줄처럼, 최솟값과 최댓값을 설정하여 비교해야 한다.