問題
實現(xiàn)一個函數(shù)君编，檢查一棵二叉樹是否為二叉搜索樹。
示例 1:
輸入:
2
/ \
1 3
輸出: true
示例 2:
輸入:
5
/ \
1 4
/ \
3 6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]笋粟。
根節(jié)點的值為 5 ，但是其右子節(jié)點值為 4 巴比。
思路
遞歸
二叉搜索樹：根節(jié)點值大于左子樹節(jié)點最大值闷哆，小于右子樹節(jié)點最小值。
左右子樹也要滿足二叉搜索樹性質蝠引。
代碼
Python3
# 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)
# 輔助函數(shù)
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_)
