Validate Binary Search Tree

Question

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
An example:

   1
  / \
 2   3
    /
   4
    \
     5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

题解1 - recursion

按照题中对二叉搜索树所给的定义递归判断，我们从递归的两个步骤出发分析：

  1. 基本条件/终止条件 - 返回值需斟酌。
  2. 递归步/条件递归 - 能使原始问题收敛。

终止条件好确定——当前节点为空，或者不符合二叉搜索树的定义，返回值分别是什么呢？先别急，分析下递归步试试先。递归步的核心步骤为比较当前节点的key和左右子节点的key大小，和定义不符则返回false, 否则递归处理。从这里可以看出在节点为空时应返回true, 由上层的其他条件判断。但需要注意的是这里不仅要考虑根节点与当前的左右子节点，还需要考虑左子树中父节点的最小值和右子树中父节点的最大值。否则程序在[10,5,15,#,#,6,20] 这种 case 误判。

由于不仅需要考虑当前父节点，还需要考虑父节点的父节点... 故递归时需要引入上界和下界值。画图分析可知对于左子树我们需要比较父节点中最小值，对于右子树则是父节点中的最大值。又由于满足二叉搜索树的定义时，左子结点的值一定小于根节点，右子节点的值一定大于根节点，故无需比较所有父节点的值，使用递推即可得上界与下界，这里的实现非常巧妙。

# 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 ValidBST(self, root, min, max):
        if root == None:
            return True
        if root.val <= min or root.val >= max:
            return False
        return self.ValidBST(root.left, min, root.val) and self.ValidBST(root.right, root.val, max)

    def isValidBST(self, root):
        return self.ValidBST(root, -2147483648, 2147483647)

# 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 isValidBST(self, root):

        def dfs(root, minval, maxval):
            if root is None:
                return True
            return minval < root.val < maxval and dfs(root.left, minval, root.val) and dfs(root.right, root.val, maxval)

        return dfs(root, -1<<32, 1<<32)

复杂度分析

递归遍历所有节点，时间复杂度为 $$O(n)$$, 使用了部分额外空间，空间复杂度为 $$O(1)$$.

题解2 - iteration

联想到二叉树的中序遍历。 TBD

Reference

results matching ""

    No results matching ""