leetcode8/RecoveryBinarySearchTree.java at master · 1code/leetcode8 · GitHub

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
61
62
63
64
65
66
67
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void recoverTree(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        TreeNode[] mess = new TreeNode[2];
        TreeNode[] pre = new TreeNode[1];
        recoverTree(root, pre, mess);
        int tmp = mess[0].val;
        mess[0].val = mess[1].val;
        mess[1].val = tmp;
    }

    //Constant Space solution
    public void recoverTree(TreeNode node, TreeNode[] pre, TreeNode[] mess){
        if(node != null){
            recoverTree(node.left, pre, mess);
            if(pre[0] != null && pre[0].val > node.val){
                if(mess[0] == null)
                    mess[0] = pre[0];
                mess[1] = node;
            }
            pre[0] = node;
            recoverTree(node.right, pre, mess);
        }
    }

    //O(N) space solution
    public void walkThrough(TreeNode root){
        ArrayList<TreeNode> inOrder = new ArrayList<TreeNode>();
        inOrderTraverse(root, inOrder);
        int first = 0, second = inOrder.size() - 1;
        for(int i = 0;i < inOrder.size(); ++i){
            if(inOrder.get(i).val > inOrder.get(i + 1).val){
                first = i;
                break;
            }
        }
        for(int j = second; j >= 0; --j){
            if(inOrder.get(j).val < inOrder.get(j - 1).val){
                second = j;
                break;
            }
        }
        int tmp = inOrder.get(first).val;
        inOrder.get(first).val = inOrder.get(second).val;
        inOrder.get(second).val = tmp;
    }

    public void inOrderTraverse(TreeNode root, ArrayList<TreeNode> inOrder){
        if(root != null){
            if(root.left != null)
                inOrderTraverse(root.left, inOrder);
            inOrder.add(root);
            if(root.right != null)
                inOrderTraverse(root.right, inOrder);
        }
    }
}