Validate Binary Search Tree Leetcode 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.
定義に基づいてhttp://en.wikipedia.org/wiki/Binary_search_tree
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. The left and right subtree each must also be a binary search tree. Each node can have up to two successor nodes. There must be no duplicate nodes. A unique path exists from the root to every other node.
左サブツリーはノードが右サブツリーより小さく、重複する値はありません.左右のノードとルートノードの値を比較するたびに、1つのノードが条件を満たさない限りFALSEに戻ります.
we compare the left, right node key with root key. If any of the condition cannot match the requirement, we return False.
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.
定義に基づいてhttp://en.wikipedia.org/wiki/Binary_search_tree
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. The left and right subtree each must also be a binary search tree. Each node can have up to two successor nodes. There must be no duplicate nodes. A unique path exists from the root to every other node.
左サブツリーはノードが右サブツリーより小さく、重複する値はありません.左右のノードとルートノードの値を比較するたびに、1つのノードが条件を満たさない限りFALSEに戻ります.
we compare the left, right node key with root key. If any of the condition cannot match the requirement, we return False.
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a boolean
def testnode(self,root,minval,maxval):
if root==None:
return True
if root.val>maxval or root.val<minval:
return False
return self.testnode(root.left,minval,root.val-1) and self.testnode(root.right,root.val+1,maxval)
def isValidBST(self, root):
minval=-3147483648
maxval=3147483648
return self.testnode(root,minval,maxval)