【LeetCode with Python】 98. Validate Binary Search Tree

题目

原题页面:https://leetcode.com/problems/validate-binary-search-tree/
本文地址:http://leetcode.xnerv.wang/validate-binary-search-tree/
题目类型:Medium
难度评价:Tree, Depth-first Search
类似题目:(M) Binary Tree Inorder Traversal

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.

    confused what "{1,#,2,3}" means?
    OJ's Binary Tree Serialization:

    The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
    Here's an example:

     1<br/>
    / \<br/>
    
    2 3
      /<br/>
     4<br/>
      \<br/>
       5<br/>
    

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

分析

检查一颗二叉树是不是有效的二叉搜索树BST。注意BST的定义,不仅仅左孩子结点的值比当前结点小,左子树上所有结点的值都要比当前结点小(BST跟heap是不同,heap只要求每个节点的直接左节点比直接右节点小即可)。右子树上所有结点的值则都要比当前结点大。使用递归检查每一棵子树是不是BST,然后回溯的时候将检查结果,以及当前子树的最大和最小结点值返回给上一层递归。注意Python的return是可以返回一个元组的,相当于可以同时return多个变量,非常方便。


代码

class Solution:

    def recurIsValidBST(self, root):
        if None == root:
            return True, None, None
        elif None == root.left and None == root.right:
            return True, root.val, root.val
        else:
            left_bool, left_min, left_max = self.recurIsValidBST(root.left)
            right_bool, right_min, right_max = self.recurIsValidBST(root.right)
            cur_bool = left_bool and right_bool and (None == left_max or root.val > left_max) and (None == right_min or root.val < right_min)
            cur_max = max(root.val, left_max, right_max)
            cur_min = min(root.val, left_min, right_min)
            return cur_bool, cur_min, cur_max

    # @param root, a tree node
    # @return a boolean
    def isValidBST(self, root):
        return self.recurIsValidBST(root)[0]

results matching ""

    No results matching ""