Contents

[Golang][Leetcode][BinaryTree]刷題系列-98-Validate Binary Search Tree


98. Validate Binary Search Tree


Level : Medium

原題連結 : Click

題目 :

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid 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 :

Note

Example 1:

Input: root = [2,1,3] Output: true

Example 2:

Input: root = [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.


解題思路 :

  • 這題考察的是你對於Binary Search Tree特性的掌握度
  • 基本的特性我就不贅述了,這邊講一個大家比較會忽略掉的特性: 當BST進行inorder排序時,必然是由小到大的有序排列
  • 換言之,我們也可以用此特性去檢查BST,若它的Inorder排序並非由小到大也就代表它不符合BST
  • 以下提供兩個解法,一個是利用BST定義去完成的解法,另一個是利用inorder特性去完成的解法

Recursive解法-1

  • time complexity: O(n) , space complexity: O(1)

Runtime: 4 ms, faster than 95.20% of Go online submissions for Validate Binary Search Tree.


 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
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "math"

func isValidBST(root *TreeNode) bool {

    if root == nil {
        return true
    } 
    
    return isBST(root, math.MinInt64, math.MaxInt64)
    
}

func isBST(root *TreeNode, min int, max int) bool {
    if root == nil {
        return true
    }
    if min >= root.Val || max <= root.Val {
        return false
    }
    
    return isBST(root.Left, min, root.Val) && isBST(root.Right, root.Val, max)
}

Recursive解法-2-利用Inorder特性

  • time complexity: O(n) , space complexity: O(1)

 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
26
27
28
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isValidBST(root *TreeNode) bool {
    
    var prev *TreeNode
    var travel func(node *TreeNode) bool
    travel = func(node *TreeNode) bool {
        if node == nil {
            return true
        }
        leftRes := travel(node.Left)
       
        if prev != nil && node.Val <= prev.Val {
            return false
        }
        prev = node
        rightRes := travel(node.Right)
        return leftRes && rightRes
    }
    return travel(root)
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!