0%

leetcode每日一题-恢复二叉搜索树

Posted on In ,

恢复二叉搜索树

image1

image2

方法一：显式中序遍历

我们需要考虑两个节点被错误地交换后对原二叉搜索树造成了什么影响。对于二叉搜索树，我们知道如果对其进行中序遍历，得到的值序列是递增有序的，而如果我们错误地交换了两个节点，等价于在这个值序列中交换了两个值，破坏了值序列的递增性。

我们来看下如果在一个递增的序列中交换两个值会造成什么影响。假设有一个递增序列 $a=[1,2,3,4,5,6,7]$。如果我们交换两个不相邻的数字，例如 22 和 66，原序列变成了$a=[1,6,3,4,5,2,7]$，那么显然序列中有两个位置不满足 $a_i<a_{i+1}$，在这个序列中体现为 $6>3$，$5>2$，因此只要我们找到这两个位置，即可找到被错误交换的两个节点。如果我们交换两个相邻的数字，例如 $2$ 和 $3$，此时交换后的序列只有一个位置不满足 $a_i<a_{i+1}$。因此整个值序列中不满足条件的位置或者有两个，或者有一个。

至此，解题方法已经呼之欲出了：

  1. 找到二叉搜索树中序遍历得到值序列的不满足条件的位置。
  2. 如果有两个，我们记为 $i$ 和 $j$（$i<j$ 且 $a_i>a_{i+1}\ &&\ a_j>a_{j+1}$ )，那么对应被错误交换的节点即为 $a_i$ 对应的节点和 $a_{j+1}$对应的节点，我们分别记为 $x$ 和 $y$。
  3. 如果有一个，我们记为 $i$，那么对应被错误交换的节点即为 $a_i$对应的节点和 $a_{i+1}$对应的节点，我们分别记为 $x$ 和 $y$。
  4. 交换 $x$ 和 $y$ 两个节点即可。

实现部分，本方法开辟一个新数组来记录中序遍历得到的值序列，然后线性遍历找到两个位置 $i$ 和 $j$，并重新遍历原二叉搜索树修改对应节点的值完成修复，具体实现可以看下面的代码。

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    List<Integer> list;
18
    public void recoverTree(TreeNode root) {
19
        list = new ArrayList<Integer>();
20
        inorderTraversal(root);
21
        //找到两个顺序错误的节点
22
        int x=-1, y=-1;
23
        int n = list.size();
24
        for(int i=0; i<n-1; i++){
25
            if(list.get(i) > list.get(i+1)){
26
                y = list.get(i+1);
27
                if(x == -1){
28
                    x = list.get(i);
29
                }else{
30
                    break;
31
                }
32
            }
33
        }
34
        //恢复顺序
35
        recover(x, y, root, 0);
36
    }
37
38
    public void recover(int x, int y, TreeNode root, int count){
39
        if(root != null){
40
            if(root.val==x || root.val==y){
41
                root.val = root.val==x ? y:x;
42
                count++;
43
                if(count == 2){
44
                    return;
45
                }
46
            }
47
            recover(x, y, root.right, count);
48
            recover(x, y, root.left, count);
49
        }
50
    }
51
52
    public void inorderTraversal(TreeNode root){
53
        if(root == null){
54
            return;
55
        }
56
        inorderTraversal(root.left);
57
        list.add(root.val);
58
        inorderTraversal(root.right);
59
    }
60
}

复杂度分析：

  • 时间复杂度：$O(n)$，其中$n$为二叉搜索树的节点数。
  • 空间复杂度：$O(n)$。

方法二：隐式中序遍历

方法一是显式地将中序遍历的值序列保存在一个数组中，然后再去寻找被错误交换的节点，但我们也可以隐式地在中序遍历的过程就找到被错误交换的节点 $x$ 和 $y$。

具体来说，由于我们只关心中序遍历的值序列中每个相邻的位置的大小关系是否满足条件，且错误交换后最多两个位置不满足条件，因此在中序遍历的过程我们只需要维护当前中序遍历到的最后一个节点 $pred$，然后在遍历到下一个节点的时候，看两个节点的值是否满足前者小于后者即可，如果不满足说明找到了一个交换的节点，且在找到两次以后就可以终止遍历。

这样我们就可以在中序遍历中直接找到被错误交换的两个节点 $x$ 和 $y$，不用显式建立数组。

1
class Solution {
2
    public void recoverTree(TreeNode root) {
3
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
4
        TreeNode x = null, y = null, pred = null;
5
6
        while (!stack.isEmpty() || root != null) {
7
            while (root != null) {
8
                stack.push(root);
9
                root = root.left;
10
            }
11
            root = stack.pop();
12
            if (pred != null && root.val < pred.val) {
13
                y = root;
14
                if (x == null) {
15
                    x = pred;
16
                } else {
17
                    break;
18
                }
19
            }
20
            pred = root;
21
            root = root.right;
22
        }
23
24
        swap(x, y);
25
    }
26
27
    public void swap(TreeNode x, TreeNode y) {
28
        int tmp = x.val;
29
        x.val = y.val;
30
        y.val = tmp;
31
    }
32
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(h)$，$h$是二叉搜索树的高度。

方法三：Morris中序遍历

Morris 遍历算法，该算法能将非递归的中序遍历空间复杂度降为 $O(1)$。算法流程如下：

  1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。 $curr=curr.right$

  2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点,也就是当前节点的左子树上最右的节点，为$mostRight$

    a) 如果前驱节点（$mostRight$）的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。$curr=curr.left$

    b) 如果前驱节点（$mostRight$）的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。$curr=curr.right$

  3. 重复以上1、2直到当前节点为空。

特点就是前驱节点有一个指针指向后继节点，因此遍历的时候可以沿着这个指针从前驱节点到达后继节点。

1
class Solution {
2
    public void recoverTree(TreeNode root) {
3
        TreeNode x = null, y = null, pred = null, predecessor = null;
4
5
        while (root != null) {
6
            if (root.left != null) {
7
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
8
                predecessor = root.left;
9
                while (predecessor.right != null && predecessor.right != root) {
10
                    predecessor = predecessor.right;
11
                }
12
                
13
                // 让 predecessor 的右指针指向 root，继续遍历左子树
14
                if (predecessor.right == null) {
15
                    predecessor.right = root;
16
                    root = root.left;
17
                }
18
                // 说明左子树已经访问完了，我们需要断开链接
19
                else {
20
                    if (pred != null && root.val < pred.val) {
21
                        y = root;
22
                        if (x == null) {
23
                            x = pred;
24
                        }
25
                    }
26
                    pred = root;
27
28
                    predecessor.right = null;
29
                    root = root.right;
30
                }
31
            }
32
            // 如果没有左孩子，则直接访问右孩子
33
            else {
34
                if (pred != null && root.val < pred.val) {
35
                    y = root;
36
                    if (x == null) {
37
                        x = pred;
38
                    }
39
                }
40
                pred = root;
41
                root = root.right;
42
            }
43
        }
44
        swap(x, y);
45
    }
46
47
    public void swap(TreeNode x, TreeNode y) {
48
        int tmp = x.val;
49
        x.val = y.val;
50
        y.val = tmp;
51
    }
52
}

复杂度分析：

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$