算法题--判断树结构是否为合法的二叉搜索树

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