2021-07-13：恢复二叉搜索树。给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下

福大大架构师每日一题

发布于 2021-08-05 16:23:15

3170

发布于 2021-08-05 16:23:15

2021-07-13：恢复二叉搜索树。给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

福大大答案2021-07-13：

大思路是求中序遍历，找逆序。一共有14种情况。如果是错误节点位置交换，题超难。如果是错误节点值交换，相对简单。实际上，错误节点位置交换才是正路，但leetcode没那么考。代码是错误节点值交换+莫里斯遍历。想看错误节点位置交换，请看文章末尾链接。

假设中序遍历结果是12345。14325两组降序。4和2交换。12435一组降序。4和3交换。

时间复杂度：O(N)。

空间复杂度：O(1)。

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

package main

import "fmt"

func main() {
    head := &TreeNode{val: 2}
    head.left = &TreeNode{val: 3}
    head.right = &TreeNode{val: 1}
    recoverTree(head)
    fmt.Println(head.val)
    fmt.Println(head.left.val)
    fmt.Println(head.right.val)
}

// 不要提交这个类
type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

// 如果能过leetcode，只需要提交这个方法即可
// 但其实recoverTree2才是正路，只不过leetcode没有那么考
func recoverTree(root *TreeNode) {
    errors := twoErrors(root)
    if errors[0] != nil && errors[1] != nil {
        errors[0].val, errors[1].val = errors[1].val, errors[0].val
    }
}

func twoErrors(head *TreeNode) []*TreeNode {
    ans := make([]*TreeNode, 2)
    if head == nil {
        return ans
    }
    cur := head
    var mostRight *TreeNode
    var pre *TreeNode
    var e1 *TreeNode
    var e2 *TreeNode
    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
            }
        }
        if pre != nil && pre.val >= cur.val {
            if e1 == nil {
                e1 = pre
            }
            e2 = cur
        }
        pre = cur
        cur = cur.right
    }
    ans[0] = e1
    ans[1] = e2
    return ans
}

执行结果如下：