长大后想做什么？做回小孩！

0%

LeetCode——恢复二叉搜索树

发表于 更新于 分类于 Valine：
本文字数： 329

NO.99 恢复二叉搜索树 困难

G4KGUe.png

G4KlDK.png

思路一：中序遍历 本题只需要交换节点的值就可以了，不需要真的交换两个节点。

难点就是如何找到需要交换的两个值。例如示例2中的树，中序遍历得到1324，需要交换2和3的位置。

看别人的题解中总结的，发现需要交换的两个节点的规律如下：

  1. 第一个需要交换的节点是：中序遍历中第一个大于下一个节点的节点即第一个违背递增的节点，在上例中就是3。
  2. 第二个需要交换的节点是：从第一个被找到的节点之后开始，中序遍历中第一个小于前一个节点的节点即第二个违背递增的节点，在上例中就是2。

中序遍历两种实现：

  1. 递归实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    TreeNode first;//记录第一个需要交换的节点
    TreeNode second;//记录第二个需要交换的节点
    TreeNode pre = new TreeNode(Integer.MIN_VALUE);//当前遍历节点的前一个节点

    public void recoverTree(TreeNode root) {
        //中序遍历找到两个节点
        inorderTraversal(root);
        //交换两个节点的值
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    private void inorderTraversal(TreeNode root) {
        if (root == null) return;
        inorderTraversal(root.left);
        //第一个节点是，大于后一个节点的节点
        if (first == null && pre.val > root.val) first = pre;
        //第二个节点是在第一个节点之后，小于前一个节点的节点
        if (first != null && pre.val > root.val) second = root;
        pre = root;
        inorderTraversal(root.right);
    }

    时间复杂度：O(n)

    空间复杂度：O(n)

  2. 迭代实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public void recoverTree(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode first = null;//记录第一个需要交换的节点
        TreeNode second = null;//记录第二个需要交换的节点
        TreeNode pre = new TreeNode(Integer.MIN_VALUE);//当前遍历节点的前一个节点
        //中序遍历找到两个节点
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (first == null && pre.val > root.val) first = pre;
            if (first != null && pre.val > root.val) second = root;
            pre = root;
            root = root.right;
        }
        //交换节点值
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    时间复杂度：O(n)

    空间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github