2021-04-12:判断二叉树是否是搜索二叉树?
【摘要】 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...
2021-04-12:判断二叉树是否是搜索二叉树?
福大大 答案2021-04-12:
中序遍历有序即可。
1.递归。
2.莫里斯遍历。
代码用golang编写。代码如下:
package main
import "fmt"
const INT_MAX = int(^uint(0) >> 1)
const INT_MIN = ^INT_MAX
func 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
}
执行结果如下:
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)