mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 00:25:22 +08:00
53 lines
1.2 KiB
Go
53 lines
1.2 KiB
Go
package leetcode
|
||
|
||
import "math"
|
||
|
||
import (
|
||
"github.com/halfrost/LeetCode-Go/structures"
|
||
)
|
||
|
||
// TreeNode define
|
||
type TreeNode = structures.TreeNode
|
||
|
||
/**
|
||
* Definition for a binary tree node.
|
||
* type TreeNode struct {
|
||
* Val int
|
||
* Left *TreeNode
|
||
* Right *TreeNode
|
||
* }
|
||
*/
|
||
|
||
// 解法一，直接按照定义比较大小，比 root 节点小的都在左边，比 root 节点大的都在右边
|
||
func isValidBST(root *TreeNode) bool {
|
||
return isValidbst(root, math.Inf(-1), math.Inf(1))
|
||
}
|
||
func isValidbst(root *TreeNode, min, max float64) bool {
|
||
if root == nil {
|
||
return true
|
||
}
|
||
v := float64(root.Val)
|
||
return v < max && v > min && isValidbst(root.Left, min, v) && isValidbst(root.Right, v, max)
|
||
}
|
||
|
||
// 解法二，把 BST 按照左中右的顺序输出到数组中，如果是 BST，则数组中的数字是从小到大有序的，如果出现逆序就不是 BST
|
||
func isValidBST1(root *TreeNode) bool {
|
||
arr := []int{}
|
||
inOrder(root, &arr)
|
||
for i := 1; i < len(arr); i++ {
|
||
if arr[i-1] >= arr[i] {
|
||
return false
|
||
}
|
||
}
|
||
return true
|
||
}
|
||
|
||
func inOrder(root *TreeNode, arr *[]int) {
|
||
if root == nil {
|
||
return
|
||
}
|
||
inOrder(root.Left, arr)
|
||
*arr = append(*arr, root.Val)
|
||
inOrder(root.Right, arr)
|
||
}
|