leetcode(99) Recover Binary Search Tree

发表于 | 分类于

Description

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

  • A solution using O(n) space is pretty straight forward.
  • Could you devise a constant space solution?

解法

我最终采用的是O(n)的算法，可以用O(1)实现，但是太巧妙了，不太好想，我选择放弃。对于二叉排序树，可以建立其与有序数组的联系，方便处理一些问题，而二叉排序树的中序遍历即为有序数组。对于只变换一次的数组，要达到完全有序，有两种情况：

a. 1，2，4，3，5

b. 1，2，5，4，3

观察发现，出现了相邻的逆序数时，可以先假设就是交换这两个数，如果之后还是出现了相邻的逆序数，则更新待更新的数。

具体而言，采用三个指针，pre用于逆序数的探测，first，second用于记录待交换的数。

具体代码如下：

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
class Solution {
    TreeNode pre;
    TreeNode first;
    TreeNode second;

    public void recoverTree(TreeNode root) {
        pre = null;
        first = null;
        second = null;
        inorde(root);
        if (second != null && first != null) {
            int tmp = second.val;
            second.val = first.val;
            first.val = tmp;
        }
    }

    void inorde(TreeNode root) {
        if (root == null) {
            return;
        }
        inorde(root.left);
        if (pre == null) {
            pre = root;
        } else {
            if (pre.val > root.val) {
                if (first == null) {
                    first = pre;

                }
                second = root;
            }
            pre = root;
        }
        inorde(root.right);
    }
}