【leetcode】-98. Validate Binary Search Tree 유효한 두 갈래 검색 트리

1540 단어 LeetCode

Validate Binary Search Tree

  • 제목
  • 귀속
  • python 코드

  • 제목


    Given a binary tree, determine if it is a valid binary search tree (BST).
    Assume a 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:
      2
     / \
    1   3
    

    Input: [2,1,3] Output: true
    Example 2:
        5
       / \
      1   4
     /      \
    3        6
    

    Input: [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.

    차례로 돌아가다


    두 갈래 검색 트리도 두 갈래 정렬 트리로 나무의 뿌리 결점 값이 왼쪽 결점 값보다 크고 오른쪽 결점 값보다 작다.그러면 먼저 근결점이 조건을 충족시키는지 판단한 다음에 좌우 결점을 두루 돌아다닌다.

    python 코드

    # 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) -> bool:
            return self.isBST(root,None,None)
        
        def isBST(self,root,l,r):
            if not root:
                return True
            if l and l.val >= root.val:
                return False
            if r and r.val <= root.val:
                return False
            return self.isBST(root.left,l,root) and self.isBST(root.right,root,r)
    

    좋은 웹페이지 즐겨찾기