Golang:
思路:这题最简单的思路,因为二叉搜索树中序遍历的特性,使得我们可以遍历所有值,找到被交换的那两位,然后把他们重新交换回来。这里给出morris算法实现(可能是这题真正最大的价值)
代码如下:
func recoverTree(root *TreeNode) {
//还是应该理解为找逆序对,使用中序遍历
var pre, x, y *TreeNode
for root != nil {
if root.Left != nil {
node := root.Left
for node.Right != nil && node.Right != root {
node = node.Right
}
if node.Right == nil {
node.Right = root
root = root.Left
} else {
if pre != nil && root.Val < pre.Val {
y = root
if x == nil {
x = pre
}
}
pre = root
node.Right = nil
root = root.Right
}
} else {
if pre != nil && root.Val < pre.Val {
y = root
if x == nil {
x = pre
}
}
pre = root
root = root.Right
}
}
x.Val, y.Val = y.Val, x.Val
}
有疑问加站长微信联系(非本文作者)