LeetCode 99. 恢复二叉搜索树

题目来源于 LeetCode 的第 99 题，难度为：中等。目前的通过率是61.9%。

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

首先说下二叉搜索树的性质，就是根节点的左子树上的值都比根节点的值小，根节点的右子树上的值都比根节点的值大【如上图的右边的那颗树】。其特性满足一个性质，就是使用中序遍历来打印二叉搜索树时，是一个升序的序列，比如上图右边的二叉搜索树使用中序遍历的打印结果就是：1->2->3->4。

因为题目中说：该树中的两个节点被错误地交换，所以只有2种情况的错误：
1. 2个错误是比邻的
2. 2个错误是分开的

看下面的图例：

算法解题思路讲解：

使用中序遍历这颗二叉树

在遍历的时候加入判断逻辑，目标是找到被错误交换的2个节点

交换这两个节点的 val。

重点是第二步: 如何找到这2个被错误交换的节点？

分析：
正常的二叉搜索树的中序遍历返回的结果是一个升序的序列。因此，如果我们发现后面节点的值小于前面节点的值，那说明找到错误节点；比如44、22和42、18都是后面的值小于前面的值。说明错误节点就是这两处。

有2个错误节点：
第一个错误节点：第一个逆序对中的较大节点。【因为交换，肯定是把大的数交换到前面去了】
第二个错误节点：最后一个逆序对中的较小节点。【因为交换，把小的数交换到后面去了】

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    var prev: TreeNode?
    var second: TreeNode?
    var first: TreeNode?
    func recoverTree(_ root: TreeNode?) {
        guard let root = root else { return }
        findWrongNodes(root)
        if let f = first, let s = second {
            let temp = f.val
            f.val = s.val
            s.val = temp
        }
    }
 
    private func findWrongNodes(_ root: TreeNode?) {
        guard let root = root else { return }
        findWrongNodes(root.left)  
        if let prevNode = prev, prevNode.val > root.val {
            second = root
            if first != nil { return }
            first = prev
        }
        prev = root
        findWrongNodes(root.right)
    }
}

代码解析：
我们写了2个参数来记录2个错误的节点，分别为first、second。并且写了一个新的函数findWrongNodes(_ root: TreeNode?) {}来进行递归也就是中序遍历来查找错误的节点。

接下来就是中序遍历中插入的逻辑。如果 prev.val > root.val, 就执行 second = root,因为是递归调用，这个判断会被执行2次，所以second = root就会被执行2次【因为只有2个错误的节点，prev.val > root.val只有2次机会进来】，只会保留最后一次执行的值，也就是最后一个逆序对中的较小节点，刚好是我们想要的，所以不需要加任何判断和过滤。

但first的赋值不能不加过滤条件了，为了避免被覆盖，就加了一个判断if first != nil。只赋值一次就行了。

最后找到2个节点后，回到函数recoverTree(_ root: TreeNode?) {}进行值的替换。从而完成二叉搜索树的恢复。

总结
今天主要分享了，这道二叉搜索树恢复的解法。其中用到的主要是递归的思想，然后在遍历的时候插入代码逻辑。所以掌握递归这个编程技巧是真的非常非常的重要。

欢迎关注【无量测试之道】公众号，回复【领取资源】
Python编程学习资源干货、
Python+Appium框架APP的UI自动化、
Python+Selenium框架Web的UI自动化、
Python+Unittest框架API自动化、
资源和代码免费送啦~
文章下方有公众号二维码，可直接微信扫一扫关注即可。

备注：我的个人公众号已正式开通，致力于测试技术的分享，包含：大数据测试、功能测试，测试开发，API接口自动化、测试运维、UI自动化测试等，微信搜索公众号：“无量测试之道”，或扫描下方二维码：

添加关注，让我们一起共同成长！