package leetcode;

/**
 * https://leetcode.com/problems/increasing-order-search-tree/
 */
public class Problem897 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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

//    TreeNode cur;
//    public TreeNode increasingBST(TreeNode root) {
//        TreeNode ans = new TreeNode(0);
//        cur = ans;
//        inorder(root);
//        return ans.right;
//    }
//
//    public void inorder(TreeNode node) {
//        if (node == null) return;
//        inorder(node.left);
//        node.left = null;
//        cur = node;
//        cur.right = cur;
//        inorder(node.right);
//    }

    public TreeNode increasingBST(TreeNode root) {
        TreeNodeRef ref = new TreeNodeRef();
        increasingBST(root, ref);
        return ref.root;
    }

    private static class TreeNodeRef {
        private TreeNode root;
        private TreeNode node;
    }

    private static void increasingBST(TreeNode node, TreeNodeRef ref) {
        if (node == null) {
            return;
        }
        increasingBST(node.left, ref);
        if (ref.root == null) {
            ref.root = node;
            ref.node = node;
        } else {
            ref.node.left = null;
            ref.node.right = node;
            ref.node = node;
        }
        increasingBST(node.right, ref);
    }

    private static void print(TreeNode node) {
        for (TreeNode n = node; n != null; n = n.right) {
            if (n.left != null) {
                throw new RuntimeException("Wrong!");
            }
            System.out.println(n.val);
        }
    }

    public static void main(String[] args) {
        Problem897 prob = new Problem897();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.left.left.left = new TreeNode(1);
        root.right = new TreeNode(6);
        root.right.right = new TreeNode(8);
        root.right.right.left = new TreeNode(7);
        root.right.right.right = new TreeNode(9);

        print(prob.increasingBST(root));
        print(prob.increasingBST(new TreeNode(1)));
    }
}

@@ -277,434 +277,8 @@
  %7D%0A%0A
-//    TreeNode cur;%0A//    public TreeNode increasingBST(TreeNode root) %7B%0A//        TreeNode ans = new TreeNode(0);%0A//        cur = ans;%0A//        inorder(root);%0A//        return ans.right;%0A//    %7D%0A//%0A//    public void inorder(TreeNode node) %7B%0A//        if (node == null) return;%0A//        inorder(node.left);%0A//        node.left = null;%0A//        cur = node;%0A//        cur.right = cur;%0A//        inorder(node.right);%0A//    %7D%0A%0A
     
@@ -704,32 +704,58 @@
 ode.left, ref);%0A
+        node.left = null;%0A
         if (ref.
@@ -849,42 +849,8 @@
 e %7B%0A
-            ref.node.left = null;%0A
     
@@ -911,32 +911,32 @@
 node;%0A        %7D%0A
+
         increasi
@@ -968,851 +968,7 @@
    %7D
-%0A%0A    private static void print(TreeNode node) %7B%0A        for (TreeNode n = node; n != null; n = n.right) %7B%0A            if (n.left != null) %7B%0A                throw new RuntimeException(%22Wrong!%22);%0A            %7D%0A            System.out.println(n.val);%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem897 prob = new Problem897();%0A        TreeNode root = new TreeNode(5);%0A        root.left = new TreeNode(3);%0A        root.left.left = new TreeNode(2);%0A        root.left.right = new TreeNode(4);%0A        root.left.left.left = new TreeNode(1);%0A        root.right = new TreeNode(6);%0A        root.right.right = new TreeNode(8);%0A        root.right.right.left = new TreeNode(7);%0A        root.right.right.right = new TreeNode(9);%0A%0A        print(prob.increasingBST(root));%0A        print(prob.increasingBST(new TreeNode(1)));%0A    %7D
 %0A%7D%0A

Solve problem 897