问题

这是我写的方法，一个元素[0]输入这种情况下，我本地跑出来是 BST，但是 Leetcode submit 结果确实不是

package main

import (
	"fmt"
)

const MaxUint = ^uint(0)
const MinUint = 0
const MaxInt = int(MaxUint >> 1)
const MinInt = -MaxInt - 1

var preData = MinInt

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}
	isValid := isValidBST(root.Left)
	if !isValid || preData >= root.Val {
		return false
	}
	preData = root.Val
	isValid = isValidBST(root.Right)
	return isValid
}

func main() {
	root := &TreeNode{
		Val:   0,
		Left:  nil,
		Right: nil,
	}
	res := isValidBST(root)
	if res {
		fmt.Printf("Tree is valid BST \n")
	} else {
		fmt.Printf("Tree is not valid BST \n")
	}
}

是我写的有问题吗？

root

treenode

isvalidbst

const

9 条回复 • 2019-07-26 17:09:01 +08:00

Hsinyao

2019-07-21 18:48:31 +08:00 via iPhone

手机上看代码排版有问题，我大致看了下，你的思路应该是中序遍历，如果所有结点都比上一个结点大，就判定为 BST ？
我当时也是这么写的，同样也是卡在 0 这个用例上，当时我在 leetcode 网页上调试运行可以通过，提交就不给过。也很迷。。。。

visitant

2019-07-21 21:39:13 +08:00

你的解法是不是有点问题啊？另外我猜测可能是因为 preData 是个全局变量，在之前的测试用例里已经被修改为其他的值了？

visitant

2019-07-21 21:41:57 +08:00

func isValidBST(root *TreeNode) bool {
preData = MinInt
return isValidBST1(nil)
}

func isValidBST1(root *TreeNode) bool {
if root == nil {
return true
}
isValid := isValidBST1(root.Left)
if !isValid || preData <= root.Val {
return false
}
preData = root.Val
isValid = isValidBST1(root.Right)
return isValid
}

验证了下，应该是因为全局变量，这样子就可以过[0]的用例了

visitant

2019-07-21 21:43:22 +08:00

@visitant 哎呀，这个代码有问题

visitant

2019-07-21 21:45:17 +08:00

func isValidBST(root *TreeNode) bool {
preData = MinInt
return isValidBST1(root)
}

func isValidBST1(root *TreeNode) bool {
if root == nil {
return true
}
isValid := isValidBST1(root.Left)
if !isValid || preData >= root.Val {
return false
}
preData = root.Val
isValid = isValidBST1(root.Right)
return isValid
}

这样可以过测试用例了，就是因为全局变量的原因，会把前一个测试用例的 preData 保存下来

salamanderMH

2019-07-21 21:47:38 +08:00 via Android

@visitant 我猜也是全局变量的问题，哈哈

carlclone

2019-07-21 22:52:48 +08:00

leetcode 的 go 全局变量有问题 , 我都是用一个结构体来保存全局变量

salamanderMH

2019-07-26 11:55:48 +08:00

@carlclone @visitant
我修改了一下代码，这样就行了
const MaxUint = ^uint(0)
const MinUint = 0
const MaxInt = int(MaxUint >> 1)
const MinInt = -MaxInt - 1

func isValidBST(root *TreeNode) bool {
preData := MinInt
return isValidBSTInner(root, &preData)
}

func isValidBSTInner(root *TreeNode, preData *int) bool {
if root == nil {
return true
}
isValid := isValidBSTInner(root.Left, preData)
if !isValid || *preData >= root.Val {
return false
}
*preData = root.Val
isValid = isValidBSTInner(root.Right, preData)
return isValid
}

carlclone

2019-07-26 17:09:01 +08:00

@salamanderMH 像楼上那样写不就好了, 干嘛要传参 , 也就是每次 test 都重新赋值一下

const MaxUint = ^uint(0)
const MinUint = 0
const MaxInt = int(MaxUint >> 1)
const MinInt = -MaxInt - 1

var preData int

func isValidBST(root *TreeNode) bool {
preData = MinInt
return isValidBSTInner(root)
}

func isValidBSTInner(root *TreeNode) bool {
if root == nil {
return true
}
isValid := isValidBSTInner(root.Left)
if !isValid || preData >= root.Val {
return false
}
preData = root.Val
isValid = isValidBSTInner(root.Right)
return isValid
}

Leetcode 98 题，判断是否为 BST？

问题