2021-04-12：判断二叉树是否是搜索二叉树？
16lz
2021-04-13
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代码
评论
每一份赞赏源于懂得
赞赏
0人进行了赞赏支持
更多相关文章
- 图 - 邻接表深度优先遍历(C语言)
- 图 -邻接表广度优先遍历(C语言)
- 图 - 邻接矩阵广度优先遍历(C语言)
- 图 - 邻接矩阵深度优先遍历(C语言)
- 浅谈递归 II
- [face_算法篇]：常见的二分、递归、选择、插入、冒泡、快排、归并
- 2021-04-04：给定一个非负数组arr，和一个正数m。 返回arr的所有子序
- 开眼界！Python 遍历文件可以这样做！
- 2021-04-02：给定一个正方形或者长方形矩阵matrix，实现zigzag打印。