package leetcode;

/**
 * https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
 */
public class Problem889 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "" + val;
        }
    }

    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        int[] preIndex = new int[pre.length + 1];
        for (int i = 0; i < pre.length; i++) {
            preIndex[pre[i]] = i;
        }
        return construct(pre, post, preIndex, new Index(post.length - 1), 0, post.length - 1);
    }

    private static class Index {
        private int val;

        public Index(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "" + val;
        }
    }

    private static TreeNode construct(int[] pre, int[] post, int[] preIndex, Index postIndex,
                                      int preBeginIndex, int preEndIndex) {
        if (preBeginIndex == preEndIndex) {
            return new TreeNode(pre[preBeginIndex]);
        }
        int index = preIndex[post[postIndex.val]];
        TreeNode node = new TreeNode(pre[index]);
        postIndex.val--;
        int midIndex = preIndex[post[postIndex.val]];
        node.right = construct(pre, post, preIndex, postIndex,
            midIndex, preEndIndex);
        postIndex.val--;
        node.left = construct(pre, post, preIndex, postIndex,
            preBeginIndex + 1, midIndex - 1);
        return node;
    }

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

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

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

    public static void main(String[] args) {
        Problem889 prob = new Problem889();
//        TreeNode root = prob.constructFromPrePost(
//            new int[]{1, 2, 4, 5, 3, 6, 7}, new int[]{4, 5, 2, 6, 7, 3, 1});
        TreeNode root = prob.constructFromPrePost(
            new int[]{1, 2, 4, 5, 3, 6, 8, 7, 9}, new int[]{4, 5, 2, 8, 6, 9, 7, 3, 1});

        preOrder(root);
        System.out.println();

        postOrder(root);
        System.out.println();

//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);
//        root.left.left = new TreeNode(4);
//        root.left.right = new TreeNode(5);
//        root.right.left = new TreeNode(6);
//        root.right.right = new TreeNode(7);
//
//        preOrder(root);
//        System.out.println();
//
//        postOrder(root);
//        System.out.println();

//        root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);
//        root.left.left = new TreeNode(4);
//        root.left.right = new TreeNode(5);
//        root.right.left = new TreeNode(6);
//        root.right.right = new TreeNode(7);
//        root.right.left.left = new TreeNode(8);
//        root.right.left.right = new TreeNode(10);
//        root.right.right.right = new TreeNode(9);
//
//        preOrder(root);
//        System.out.println();
//
//        postOrder(root);
//        System.out.println();
    }
}

@@ -300,101 +300,8 @@
    %7D
-%0A%0A        @Override%0A        public String toString() %7B%0A            return %22%22 + val;%0A        %7D
 %0A   
@@ -745,101 +745,8 @@
    %7D
-%0A%0A        @Override%0A        public String toString() %7B%0A            return %22%22 + val;%0A        %7D
 %0A   
@@ -911,32 +911,139 @@
  preEndIndex) %7B%0A
+        if (preBeginIndex %3E preEndIndex) %7B%0A            postIndex.val++;%0A            return null;%0A        %7D%0A
         if (preB
@@ -1271,17 +1271,20 @@
     int 
-m
+preM
 idIndex 
@@ -1391,17 +1391,20 @@
         
-m
+preM
 idIndex,
@@ -1536,17 +1536,20 @@
 ex + 1, 
-m
+preM
 idIndex 
@@ -1584,2131 +1584,7 @@
    %7D
-%0A%0A    private static void preOrder(TreeNode node) %7B%0A        if (node == null) %7B%0A            return;%0A        %7D%0A        System.out.print(node.val + %22 %22);%0A        preOrder(node.left);%0A        preOrder(node.right);%0A    %7D%0A%0A    private static void inOrder(TreeNode node) %7B%0A        if (node == null) %7B%0A            return;%0A        %7D%0A        inOrder(node.left);%0A        System.out.print(node.val + %22 %22);%0A        inOrder(node.right);%0A    %7D%0A%0A    private static void postOrder(TreeNode node) %7B%0A        if (node == null) %7B%0A            return;%0A        %7D%0A        postOrder(node.left);%0A        postOrder(node.right);%0A        System.out.print(node.val + %22 %22);%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem889 prob = new Problem889();%0A//        TreeNode root = prob.constructFromPrePost(%0A//            new int%5B%5D%7B1, 2, 4, 5, 3, 6, 7%7D, new int%5B%5D%7B4, 5, 2, 6, 7, 3, 1%7D);%0A        TreeNode root = prob.constructFromPrePost(%0A            new int%5B%5D%7B1, 2, 4, 5, 3, 6, 8, 7, 9%7D, new int%5B%5D%7B4, 5, 2, 8, 6, 9, 7, 3, 1%7D);%0A%0A        preOrder(root);%0A        System.out.println();%0A%0A        postOrder(root);%0A        System.out.println();%0A%0A//        TreeNode root = new TreeNode(1);%0A//        root.left = new TreeNode(2);%0A//        root.right = new TreeNode(3);%0A//        root.left.left = new TreeNode(4);%0A//        root.left.right = new TreeNode(5);%0A//        root.right.left = new TreeNode(6);%0A//        root.right.right = new TreeNode(7);%0A//%0A//        preOrder(root);%0A//        System.out.println();%0A//%0A//        postOrder(root);%0A//        System.out.println();%0A%0A//        root = new TreeNode(1);%0A//        root.left = new TreeNode(2);%0A//        root.right = new TreeNode(3);%0A//        root.left.left = new TreeNode(4);%0A//        root.left.right = new TreeNode(5);%0A//        root.right.left = new TreeNode(6);%0A//        root.right.right = new TreeNode(7);%0A//        root.right.left.left = new TreeNode(8);%0A//        root.right.left.right = new TreeNode(10);%0A//        root.right.right.right = new TreeNode(9);%0A//%0A//        preOrder(root);%0A//        System.out.println();%0A//%0A//        postOrder(root);%0A//        System.out.println();%0A    %7D
 %0A%7D%0A

Solve problem 889