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

Steven included in Leetcode Golang

2021-09-07 388 words 2 minutes

/leetcode98_binarytree/golang_leetcode.png

Contents

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” 我們峰頂見!!!