首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
探索世界的好奇心万岁
Udacity
网易公开课
Godel, Escher, Bach: An Eternal Golden Braid
Coding
V2EX  ›  分享发现

Leetcode 98 题,判断是否为 BST?

  •  
  •   salamanderMH · 148 天前 · 1258 次点击
    这是一个创建于 148 天前的主题,其中的信息可能已经有所发展或是发生改变。

    问题

    这是我写的方法,一个元素[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")
    	}
    }
    

    是我写的有问题吗?

    9 回复  |  直到 2019-07-26 17:09:01 +08:00
        1
    Hsinyao   148 天前 via iPhone
    手机上看代码排版有问题,我大致看了下,你的思路应该是中序遍历,如果所有结点都比上一个结点大,就判定为 BST ?
    我当时也是这么写的,同样也是卡在 0 这个用例上,当时我在 leetcode 网页上调试运行可以通过,提交就不给过。也很迷。。。。
        2
    visitant   147 天前   ♥ 1
    你的解法是不是有点问题啊?另外 我猜测可能是因为 preData 是个全局变量,在之前的测试用例里已经被修改为其他的值了?
        3
    visitant   147 天前
    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]的用例了
        4
    visitant   147 天前
    @visitant 哎呀,这个代码有问题
        5
    visitant   147 天前
    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 保存下来
        6
    salamanderMH   147 天前 via Android
    @visitant 我猜也是全局变量的问题,哈哈
        7
    carlclone   147 天前
    leetcode 的 go 全局变量有问题 , 我都是用一个结构体来保存全局变量
        8
    salamanderMH   143 天前
    @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
    }
        9
    carlclone   143 天前
    @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
    }
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2616 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 28ms · UTC 13:34 · PVG 21:34 · LAX 05:34 · JFK 08:34
    ♥ Do have faith in what you're doing.