【原】刻意练习：LeetCode实战 -- Task24. 恢复二叉搜索树

背景

本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了 三个简单、两个中等、一个困难 等级的题目，共计三十道题，利用三十天的时间完成这组刻意练习。

本次任务的知识点：树

树 是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n(n>0) 个有限节点组成的一个具有层次关系的集合。

把它叫做「树」是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

它具有以下的特点：

• 每个节点都只有有限个子节点或无子节点；

• 没有父节点的节点称为根节点；

• 每一个非根节点有且只有一个父节点；

• 除了根节点外，每个子节点可以分为多个不相交的子树；

• 树里面没有环路。

---

题目

• 题号：99

• 难度：困难

• https:///problems/recover-binary-search-tree/

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2


示例 2:

输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3


进阶:

• 使用 O(n) 空间复杂度的解法很容易实现。

• 你能想出一个只使用常数空间的解决方案吗？

---

实现

第一种：利用中序遍历

二叉搜索树是左孩子小于根节点，右孩子大于根节点的树，所以做一次中序遍历，产生的序列就是从小到大排列的有序序列。

回到这道题，题目交换了两个数字，其实就是在有序序列中交换了两个数字。而我们只需要把它还原。

交换位置有两种情况：

• 相邻的两个数字交换

[ 1 2 3 4 5 ] 中 2 和 3 进行交换，[ 1 3 2 4 5 ]，这样的话只产生一组逆序的数字（正常情况是从小到大排序，交换后产生了从大到小），3 2。

我们只需要遍历数组，找到后，把这一组的两个数字进行交换即可。

• 不相邻的两个数字交换

[ 1 2 3 4 5 ] 中 2 和 5 进行交换，[ 1 5 3 4 2 ]，这样的话其实就是产生了两组逆序的数字对。5 3 和 4 2。

所以我们只需要遍历数组，然后找到这两组逆序对，然后把第一组前一个数字和第二组后一个数字进行交换即完成了还原。

综上，在中序遍历中，只需要利用一个 pre 节点和当前节点比较，如果 pre 节点的值大于当前节点的值，那么就是我们要找的逆序的数字。分别用两个指针 first 和 second 保存即可。如果找到第二组逆序的数字，我们就把 second 更新为当前节点。最后把 first 和 second 两个的数字交换即可。

• 执行结果：通过

• 执行用时：132 ms, 在所有 C# 提交中击败了 72.41% 的用户

• 内存消耗：27.6 MB, 在所有 C# 提交中击败了 100.00% 的用户

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution
{
    public void RecoverTree(TreeNode root)
    {
        inorderTraversal(root);
        if(first == null || second == null)
            return;
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    private TreeNode pre = null;
    private TreeNode first = null;
    private TreeNode second = null;
    private void inorderTraversal(TreeNode root)
    {
        if (root == null)
        {
            return;
        }
        inorderTraversal(root.left);

        if (pre != null && pre.val > root.val)
        {
            //第一次遇到逆序对
            if (first == null)
            {
                first = pre;
                second = root;
            }
            else
            {
                //第二次遇到逆序对
                second = root;
            }
        }
        else
        {
            pre = root;
        }

        inorderTraversal(root.right);
    }
}


Python 语言

• 执行结果：通过

• 执行用时：64 ms, 在所有 Python3 提交中击败了 93.67% 的用户

• 内存消耗：14 MB, 在所有 Python3 提交中击败了 5.32% 的用户

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.inorderTraversal(root)
        if self.first is None or self.second is None:
            return None
        self.first.val, self.second.val = self.second.val, self.first.val

    def __init__(self):
        self.pre = None
        self.first = None
        self.second = None

    def inorderTraversal(self, root: TreeNode) -> None:
        if root is None:
            return None
        self.inorderTraversal(root.left)
        if self.pre is not None and self.pre.val > root.val:
            if self.first is None:
                self.first = self.pre
                self.second = root
            else:
                self.second = root
        else:
            self.pre = root
        self.inorderTraversal(root.right)


---