[Leetcode/파이썬] 98. Validate Binary Search Tree

Validate Binary Search Tree

---

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 strictly less than the node's key.
• The right subtree of a node contains only nodes with keys strictly 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

 

# 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 isValid(self, node: Optional[TreeNode], mxl, mxr) :
        if not (mxl < node.val < mxr) :
            return False

        left_val, right_val = True, True

        if node.left :
            left_val = self.isValid(node.left, mxl, node.val)
        
        if node.right :
            right_val = self.isValid(node.right, node.val, mxr)

        return left_val and right_val

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        mxl, mxr = -1<<32, 1<<32
        return self.isValid(root, mxl, mxr)

 

mxl, mxr은 node.val 의 범위를 초기 범위로 잡아서 left, right로 나누어서 DFS를 진행. 

이진탐색트리라고 했는데 완전한 트리라고 착각해서 둘 다 존재해야 True라고 줘서 많이 헤맸다.