Leetcode 98 - Validate Binary Search Tree

DocumentsAlgorithms
Algorithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. Analysis
  3. 3. Code

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 1:

Input:
    2
   / \
  1   3
Output: true

Example 2:

    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.

Analysis

这道题需要判断对于每个节点其左边的子节点是不是都小于自身，同时右边的子节点是不是都大于自身。这种要求下使用中序遍历可以按照左节点->父节点->右节点的顺序，将树的每一个节点取出，并存在序列中。如果树是一个二叉搜索树，那么生成的序列中每一个元素都应当比其左边的元素大。如果比左边的元素小或者等于都说明不满足二叉搜索树的要求。

这里采用递归的方法遍历节点，根据中序遍历的顺序，先遍历左节点，再是父节点，最后是右节点。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root == None:
            return True
        nodeOrder = []
        self.nodeAppender(root, nodeOrder)
        for i in range(len(nodeOrder)-1):
            if nodeOrder[i] >= nodeOrder[i+1]:
                return False
        return True

    def nodeAppender(self, root, nodeOrder):
        """
        :type root: TreeNode
        :type nodeOrder: List[int]
        :rtype: No return
        """
        if root:
            self.nodeAppender(root.left, nodeOrder)
            nodeOrder.append(root.val)
            self.nodeAppender(root.right, nodeOrder)
Comments