用非递归的方法重建二叉树，前序和中序

所有可以用递归的算法都可以用栈解决
非递归的方法，前序和中序，重建二叉树。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    Stack<Integer> p = new Stack<Integer>();
    Stack<TreeNode> l = new Stack<TreeNode>();
    TreeNode cur = null;
    p.push(0);
    p.push(pre.length - 1);
    p.push(0);
    p.push(in.length - 1);
    int count = 1;
    int pStart = 0;
    int pEnd = pre.length - 1;
    int iStart = 0;
    int iEnd = in.length - 1;
    TreeNode root = new TreeNode(-1);
    l.push(root);
    while( count != 0){

      iEnd = p.pop();
      iStart = p.pop();
      pEnd = p.pop();
      pStart = p.pop();
      cur = l.pop();
      count -= 1;
      int index = find(pre[pStart], in, iStart, iEnd);
      cur.val = pre[pStart];

      int lenL = index - iStart;
      if(lenL == 0){

      }else{
        p.push(pStart + 1);
        p.push(pStart + lenL);
        p.push(iStart);
        p.push(index - 1);
        count += 1;
        cur.left = new TreeNode(-1);
        l.push(cur.left);
      }
      int lenR = iEnd - index;
      if(lenR == 0){

      }else{
        p.push(pStart + lenL + 1);
        p.push(pEnd);
        p.push(index + 1);
        p.push(iEnd);
        count += 1;
        cur.right = new TreeNode(-1);
        l.push(cur.right);
      }

    }
    return root;

  }

  int find(int target, int[] all, int start , int end){
    for(int i = start; i <= end; ++i){
      if(all[i] == target) return i;
    }
    return -1;
  }
}