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代码
评论