[LeetCode] 98. Validate Binary Search Tree

题目

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:

1
2
3
4
5
Input:
    2
   / \
  1   3
Output: true

Example 2:

1
2
3
4
5
6
7
8
    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

解题报告

这题主要考查的是二叉搜索树的性质，也就是对于每一个节点来说，它左子树的所有元素都小于它，而右子树的所有元素都大于它。也就是说二叉搜索树在本题中不允许出现两个节点值相同的情况。

方法一：前序遍历检查是否满足顺序

二叉搜索树的一个重要特征是，它的前序遍历是符合大小顺序的，因为前序遍历用的是左中右的顺序，这应该就很好理解啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.traverse = []
        self.dfs(root)
        return all(a < b for a, b in zip(self.traverse, self.traverse[1:]))
        
    def dfs(self, node):
        if not node:
            return
        self.dfs(node.left)
        self.traverse.append(node.val)
        self.dfs(node.right)

方法二：另一种利用性质的递归

另一种方法来自于 Leet Code 的讨论区。这种方法的中心思想利用的是节点大小的传递性：对于每个节点来说，它的左子节点的最大值是这个节点的值，而最小值维持和这个节点的最小值相同，右子节点同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

def check_node(node, l, r):
        if not node:
            return True
        return l < node.val and node.val < r and check_node(node.left, l, node.val) and check_node(node.right, node.val, r)
    
class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        l, r = float("-inf"), float("inf")
        return check_node(root, l, r)
发布于
tags:
  • { Python }
  • { 解题报告 }
  • { LeetCode }
  • { 树 }
  • { 递归 }