恢复二叉搜索树

发表于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

LeetCode每日一题，99. Recover Binary Search Tree

先看题目描述

大意是有一颗二叉搜索树，其中的两个节点互换了位置，让我们将该二叉搜索树恢复

算法和思路

我们回忆下二叉搜索树的性质，可以想到其中根遍历序列是有序的，我们可以利用这点来解题，以递增序列 [1, 2, 3, 4] 为例，1 和 4 交换后，序列为[4, 2, 3, 1]，只有两个地方不满足 a[i] < a[i + 1]，即 i = 0 和 i = 2 时，在这里体现为 4 > 2 与 3 > 1，那么我们就可以找到交换的节点为 4 和 1，因此我们只要找到这两个位置，就可以找出交换的两个节点，若交换的是两个相邻的数字，则只有一个不满足 a[i] < a[i + 1] 的位置，同意可以找出两个交换的节点

至此解法就很明朗了，先求出给定改变后的二叉搜索树的中序遍历序列，再找到不满足 a[i] < a[i + 1] 的位置，如果有两个，我们记为 i 和 j (i < j && a[i] > a[i + 1] && a[j] > a[j + 1]) ,，那么对应的被交换节点的值即为 a[i] 与 [j + 1]；若只有一个，我们记为 i (a[i] > a[i + 1])，对应的被交换节点的值即为 a[i] 与 a[i + 1]，我们再根据找出来的值，去二叉搜索树中找出对应节点，修正他们的值即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.LinkedList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<Integer> inOrder = new LinkedList<>();

    public void recoverTree(TreeNode root) {
        List<Integer> vals = new LinkedList<>();
        inOrder(root);
        int[] nums = findTwo();
        recover(root, 2, nums[0], nums[1]);
    }

    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        inOrder.add(root.val);
        inOrder(root.right);
    }

    public int[] findTwo() {
        int n = inOrder.size();
        int x = -1;
        int y = -1;
        for (int i = 0; i < n - 1; i++) {
            if (inOrder.get(i) > inOrder.get(i + 1)) {
                y = inOrder.get(i + 1);
                if (x == -1) {
                    x = inOrder.get(i);
                }
            }
        }
        return new int[]{x, y};
    }

    public void recover(TreeNode root, int count, int x, int y) {
        if (root == null) return;
        if (root.val == x || root.val == y) {
            root.val = root.val == x ? y : x;
            if (-- count == 0) return;;
        }
        recover(root.left, count, x, y);
        recover(root.right, count, x, y);
    }
}

这个办法用时较长，运行效率较低，因为该方法在得到中根遍历序列后，遍历该序列找出交换节点的值，又要根据交换节点的值，去二叉搜索树中找出对应节点再修正他们的值，这过程做了些无用功。事实上在中根遍历的过程中，我们可以用一个 preNode 来记录遍历过程中的上一个节点，用 firstNode 和 secondNode 来记录找出来的两个交换的节点，找出两个交换的节点的方法和前面描述的基本一致，这样我们在中根遍历二叉搜索树的过程中就可以找出被交换的两个节点，然后直接交换这两个节点的值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode firstNode = null;
    TreeNode secondNode = null;
    TreeNode preNode = new TreeNode(Integer.MIN_VALUE);

    public void recoverTree(TreeNode root) {
        inOrder(root);
        int temp = firstNode.val;
        firstNode.val = secondNode.val;
        secondNode.val = temp;
    }

    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        if (firstNode == null && preNode.val > root.val) {
            firstNode = preNode;
        }
        if (firstNode != null && preNode.val > root.val) {
            secondNode = root;
        }
        preNode = root;
        inOrder(root.right);
    }
}