image.png
0. 链接
1. 题目
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.
2. 思路1: 递归
- 二叉搜索树的合法条件是，对于任意一个父节点而言，左子树的所有节点值都要小于父节点值，右子树的所有节点值都要大于父节点值
- 因此在从根节点往下搜索的时候,每个节点的值所处的区间，总有一个边界值是历史迭代过程中遗留下来的，而另一个边界值是父节点的值
- 利用递归函数来实现，函数的参数里除了包含当前要判断的节点node, 还包括其lower和upper值, 这两个值都是变量
3. 代码
# coding:utf8
# 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:
def valid(node, lower, upper):
if node is None:
return True
if upper is not None and node.val >= upper:
return False
if lower is not None and node.val <= lower:
return False
return valid(node.left, lower, node.val) and valid(node.right, node.val, upper)
return valid(root, None, None)
root1 = node = TreeNode(2)
node.left = TreeNode(1)
node.right = TreeNode(3)
root2 = node = TreeNode(5)
node.left = TreeNode(1)
node.right = TreeNode(4)
node = node.right
node.left = TreeNode(3)
node.right = TreeNode(6)
root3 = node = TreeNode(5)
node.left = TreeNode(1)
node = node.left
node.right = TreeNode(6)
root4 = node = TreeNode(1)
node.left = TreeNode(1)
root5 = node = TreeNode(3)
node.left = TreeNode(1)
node.left.left = TreeNode(0)
node.left.right = TreeNode(2)
node.right = TreeNode(5)
node.right.left = TreeNode(4)
node.right.right = TreeNode(6)
root6 = node = TreeNode(3)
node.left = TreeNode(1)
node.right = TreeNode(5)
node.left.left = TreeNode(0)
node.left.right = TreeNode(2)
node.right.left = TreeNode(4)
node.right.right = TreeNode(6)
node.left.left.left = None
node.left.left.right = None
node.left.right.left = None
node.left.right.right = TreeNode(3)
solution = Solution()
print(solution.isValidBST(root1)) # True
print(solution.isValidBST(root2)) # False
print(solution.isValidBST(root3)) # False
print(solution.isValidBST(root4)) # False
print(solution.isValidBST(root5)) # True
print(solution.isValidBST(root6)) # False
输出结果
True
False
False
False
True
False
结果
image.png
网友评论