LeetCode | 0098. Validate Binary Search Tree検証二叉検索ツリー【Python】
LeetCode 0098. Validate Binary Search Tree検証二叉探索ツリー【Medium】【Python】【二叉ツリー】
Problem
LeetCode
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:
Example 2:
に質問
スナップ
2つのツリーを指定し、有効な2つのツリーであるかどうかを判断します.
二叉検索ツリーには、次のような特徴があるとします.ノードの左サブツリーには、現在のノードより小さい数しか含まれていません. ノードの右サブツリーには、現在のノードより大きい数しか含まれていません. すべての左サブツリーと右サブツリー自体も二叉検索ツリーである必要があります.
例1:
例2:
構想
二叉木
Python 3コード
GitHubリンク
Python
Problem
LeetCode
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
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.
に質問
スナップ
2つのツリーを指定し、有効な2つのツリーであるかどうかを判断します.
二叉検索ツリーには、次のような特徴があるとします.
例1:
:
2
/ \
1 3
: true
例2:
:
5
/ \
1 4
/ \
3 6
: false
: : [5,1,4,null,null,3,6]。
5 ， 4 。
構想
二叉木
root ， 。
Python 3コード
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
return self.isValid(root, None, None)
def isValid(self, root: TreeNode, min_: TreeNode, max_: TreeNode):
if not root:
return True
if min_ != None and root.val <= min_.val:
return False
if max_ != None and root.val >= max_.val:
return False
return self.isValid(root.left, min_, root) and self.isValid(root.right, root, max_)
GitHubリンク
Python