8288分类目录 8288分类目录 8288分类目录
  当前位置:海洋目录网 » 站长资讯 » 站长资讯 » 文章详细 订阅RssFeed

2021-04-12:判断二叉树是否是搜索二叉树?

来源:本站原创 浏览:102次 时间:2022-01-06

2021-04-12:判断二叉树是否是搜索二叉树?

福大大 答案2021-04-12:

中序遍历有序即可。
1.递归。
2.莫里斯遍历。

代码用golang编写。代码如下:

package mainimport "fmt"const INT_MAX = int(^uint(0) >> 1)const INT_MIN = ^INT_MAXfunc main() {    head := &TreeNode{Val: 5}    head.Left = &TreeNode{Val: 3}    head.Right = &TreeNode{Val: 7}    head.Left.Left = &TreeNode{Val: 2}    head.Left.Right = &TreeNode{Val: 4}    head.Right.Left = &TreeNode{Val: 6}    head.Right.Right = &TreeNode{Val: 8}    ret := isBST1(head)    fmt.Println("递归:", ret)    fmt.Println("----")    ret = isBST2(head)    fmt.Println("莫里斯遍历:", ret)}//Definition for a binary tree node.type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}func isBST1(head *TreeNode) bool {    if head == nil {        return true    }    ansVal := true    ans := &ansVal    preVal := INT_MIN    pre := &preVal    process(head, pre, ans)    return *ans}func process(head *TreeNode, pre *int, ans *bool) {    if head == nil {        return    }    if *ans {        process(head.Left, pre, ans)    }    if *ans {        if *pre > head.Val {            *ans = false        } else {            *pre = head.Val        }    }    if *ans {        process(head.Right, pre, ans)    }}// 根据morris遍历改写func isBST2(head *TreeNode) bool {    if head == nil {        return true    }    cur := head    var mostRight *TreeNode    preVal := INT_MIN    for cur != nil {        mostRight = cur.Left        if mostRight != nil {            for mostRight.Right != nil && mostRight.Right != cur {                mostRight = mostRight.Right            }            if mostRight.Right == nil { //先 第一次到达                mostRight.Right = cur                cur = cur.Left                continue            } else { //后 第二次到达                mostRight.Right = nil            }        } else { //先 只有一次到达        }        //此时cur就是中序        if preVal > cur.Val {            return false        } else {            preVal = cur.Val        }        //中        cur = cur.Right    }    //后    return true}

执行结果如下:


左神java代码
评论

  推荐站点

  • At-lib分类目录At-lib分类目录

    At-lib网站分类目录汇集全国所有高质量网站,是中国权威的中文网站分类目录,给站长提供免费网址目录提交收录和推荐最新最全的优秀网站大全是名站导航之家

    www.at-lib.cn
  • 中国链接目录中国链接目录

    中国链接目录简称链接目录,是收录优秀网站和淘宝网店的网站分类目录,为您提供优质的网址导航服务,也是网店进行收录推广,站长免费推广网站、加快百度收录、增加友情链接和网站外链的平台。

    www.cnlink.org
  • 35目录网35目录网

    35目录免费收录各类优秀网站,全力打造互动式网站目录,提供网站分类目录检索,关键字搜索功能。欢迎您向35目录推荐、提交优秀网站。

    www.35mulu.com
  • 就要爱网站目录就要爱网站目录

    就要爱网站目录,按主题和类别列出网站。所有提交的网站都经过人工审查,确保质量和无垃圾邮件的结果。

    www.912219.com
  • 伍佰目录伍佰目录

    伍佰网站目录免费收录各类优秀网站,全力打造互动式网站目录,提供网站分类目录检索,关键字搜索功能。欢迎您向伍佰目录推荐、提交优秀网站。

    www.wbwb.net