[Leetcode 98] - Validate Binary Search w/ Python

 

 

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.

 

 

 

 

이진 트리가 주어졌을때 이진 탐색 트리인지 확인하는 문제

 

각 노드마다 왼쪽 ↔ 오른쪽에 있는 자식 노드들이 각자 더 작은지 ↔ 큰지 확인

 

 

 

 

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

 

 

---

 

 

 

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.

 

 

 

---

 

 

탐색 트리인지 확인하기 위해서는 각 노드에서 비교할 수 있는 가장 작은 값 그리고 가장 큰 값이 중요하다

즉, Parent 노드에서 부터 내려온 숫자를 비롯해 Child노드의 값이 포함이 되는 숫자인지 아닌지 파악하는 알고리즘 필요

 

 

1. 탐색을 시작할때 왼쪽, 오른쪽은 둘다 -infinity, infinity로 저장

2. 노드가 None이면 True

3. 왼쪽 < 현재 노드 값 < 오른쪽 비교

4. 왼쪽으로 탐색을 해야되면 오른쪽 값을 현재 확인한 노드로 수정

5. 오른쪽으로 탐색을 해야되면 왼쪽 값을 현재 확인한 노드로 수정

6. 모든 노드를 확인 했을때 탐색 트리가 맞다면 True, 아니라면 False

 

 

 

---

 

 

 

 

이해를 돕기 위해 Example 2 사진을 한번 만들어 봤다

 

☆ 5에 있을때 왼쪽 오른쪽은 둘다 [-∞, ∞ ] 다. 이때 왼쪽 자식으로 이동할때는 [-∞, 5] 오른쪽은 [5, ∞] 로 수정

☆ 1로 왔다고 가정하면 [-∞, 5] 에서 [-∞, 1]로 수정을 하겠지만 자식 노드가 더 이상 없기에 마무리

☆ 4로 왔다고 가정하면 현재 [5, ∞] 에서 비교를 해본 결과 4는 [5, ∞]에 포함되지 않는다 (4 < 5 < ∞)

☆ 즉 False로 마무리

 

 

---

 

 

class Solution:
    def isValidBST(self, root) -> bool:

        def valid(node, left, right):
            if not node:
                return True
            if not (left < node.val < right):
                return False
            
            return (valid(node.left, left, node.val) and
                    valid(node.right, node.val, right))
        
        return valid(root, float("-inf"), float("inf"))