package leetcode;

/**
 * https://leetcode.com/problems/recover-binary-search-tree/
 */
public class Problem99 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public void recoverTree(TreeNode root) {
        // TODO
    }

    private static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    private static void print(TreeNode root) {
        inOrder(root);
        System.out.println();
    }

    public static void main(String[] args) {
        Problem99 prob = new Problem99();

        TreeNode root = new TreeNode(7);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.left.right.right = new TreeNode(4);
        root.right = new TreeNode(8);
        root.right.left = new TreeNode(6);
        root.right.left.right = new TreeNode(5);
        root.right.right = new TreeNode(9);

        prob.recoverTree(root);
        print(root);
    }
}

@@ -12,16 +12,68 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.List;%0A%0A
 /**%0A * h
@@ -331,517 +331,749 @@
    p
-ublic void recoverTree(TreeNode root) %7B%0A        // TODO%0A    %7D%0A%0A    private static void inOrder(TreeNode root) %7B%0A        if (root == null) %7B%0A            return;%0A        %7D%0A        inOrder(root.left);%0A        System.out.print(root.val + %22 %22);%0A        inOrder(root.right);%0A    %7D%0A%0A    private static void print(TreeNode root) %7B%0A        inOrder(root);%0A        System.out.println(
+rivate static class Ref %7B%0A        private TreeNode node;%0A    %7D%0A%0A    public void recoverTree(TreeNode root) %7B%0A        List%3CTreeNode%3E swappedNodes = new ArrayList%3C%3E();%0A        Ref ref = new Ref();%0A        recoverTree(root, ref, swappedNodes);%0A        swap(swappedNodes.get(0), swappedNodes.get(1));%0A    %7D%0A%0A    public void recoverTree(TreeNode root, Ref ref, List%3CTreeNode%3E swappedNodes) %7B%0A        if (root == null) %7B%0A            return;%0A        %7D%0A        recoverTree(root.left, ref, swappedNodes);%0A        if (ref.node != null && ref.node.val %3E root.val) %7B%0A            if (swappedNodes.size() == 0) %7B%0A                swappedNodes.add(ref.node);%0A                swappedNodes.add(root
 );%0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem99 prob = new Problem99();%0A%0A        TreeNode root = new TreeNode(7
+    %7D else %7B%0A                swappedNodes.remove(1
 );%0A 
@@ -1083,397 +1083,294 @@
     
-root.left = new TreeNode(2);%0A        root.left.left = new TreeNode(1);%0A        root.left.right = new TreeNode(3);%0A        root.left.right.right = new TreeNode(4);%0A        root.right = new Tree
+        swappedNodes.add(root);%0A            %7D%0A        %7D%0A        ref.node = root;%0A        recoverTree(root.right, ref, swapped
 Node
-(8
+s
 );%0A    
+%7D%0A%0A
     
-root.right.left = new TreeNode(6);%0A        root.right.left.right = new TreeNode(5);%0A        root.right.right = new TreeNode(9);%0A%0A        prob.recoverTree(root);%0A        print(root)
+private static void swap(TreeNode node1, TreeNode node2) %7B%0A        int tmp = node1.val;%0A        node1.val = node2.val;%0A        node2.val = tmp
 ;%0A  

Solve problem 99