从前序和中序遍历构造二叉树

/**
总结
前序和中序的规律是
同为长为n的序列
长为k的左子树 根 长为n-k-1的右子树
根 长为k的左子树 长为n-k-1的右子树

1、确定两个序列中根所在的位置后
2、截出两个左子树序列，继续找左子树的根，将其作为上一根节点的左节点
2、截出两个右子树序列，继续找右子树的根，将其作为上一根节点的右节点
3、递归找根，直到子树为空时结束

**/

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||inorder==null){
            return null;
        }
        return travel(preorder,inorder,0 ,preorder.length-1 , 0,inorder.length-1);
    }
    public TreeNode travel(int[] preorder, int[] inorder ,int prex , int prey, int inx,int iny ){
        if(prex>prey || inx>iny){
            return null;
        }
        TreeNode node = new TreeNode(preorder[prex]);
        
        for (int k = 0 ; inx+k<=iny ; k++){ 
        //注：最好用0，若用inx作为起始，需要减去inx得到相对长度来截取后序遍历。
            if(inorder[inx+k]==preorder[prex]){
                node.left = travel(preorder,inorder,prex+1 , prex+ k+1 , inx,inx+ k-1);
                node.right = travel(preorder,inorder,prex+ k+1 , prey , inx+ k+1,iny);
                
            }
        }
        return node;
    }
}

//寻找根结点在inorder中的index
private int findRoot(int[] inorder, int[] postorder, int left, int right,int root) {
//顺序查找
while (left<right&&inorder[left] != root){
left++;
}
return left;
}
public TreeNode buildTree2(int[] inorder, int[] preorder) {
return build2(inorder,0,preorder.length-1,preorder,0,preorder.length-1);
}
//前序遍历+中序遍历 前序遍历的第一个是根结点
private TreeNode build2(int[] inorder,int ileft,int iright, int[] preorder, int pleft, int pright) {
if (pleft>pright||ileft>iright)
return null;
int rootVal=preorder[pleft];
TreeNode root = new TreeNode(rootVal);
int rootIndex = findRoot(inorder, preorder, ileft,iright,rootVal);
root.left=build2(inorder,ileft,rootIndex-1,preorder,pleft+1,pleft+rootIndex-ileft);
root.right=build2(inorder,rootIndex+1,iright,preorder,pleft+rootIndex-ileft+1,pright);
return root;
}

没看答案自己憋出来的代码。。。原理和讨论区大部分人相同，比热评减少参数效率高一点

     public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0) {
            return null;
        }
        return recursion(preorder, inorder, 0,preorder.length-1, 0);
    }
    private TreeNode recursion(int[] preorder, int[] inorder, int head,int tail, int first) {
        TreeNode root = new TreeNode(preorder[first]);
        int mid = -1;
        for(int i = head ; i<= tail; ++i) {  
            if(inorder[i] == preorder[first]) {
                mid = i;
                break;
            }
        }
        if(mid != head) root.left = recursion(preorder, inorder, head,mid-1, first+1);
        first = first + mid - head;
        if(mid != tail) root.right = recursion(preorder, inorder, mid+1,tail, first+1);      
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0)
            return null;

        return build(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }

    public TreeNode build(int[] pre, int[] in, int prestart, int preend, int instart, int inend) {
        if (prestart > preend || instart > inend)
            return null;
        int value = pre[prestart];
        TreeNode root = new TreeNode(value);
        int index = -1;
        for (int i = instart; i <= inend; i++) {
            if (in[i] == value)
                index = i;
        }

        root.left = build(pre, in, prestart+1, prestart + index-instart, instart, index - 1);
        root.right = build(pre, in, prestart+index-instart+1, preend , index + 1, inend);

        return root;
    }
}

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd)
            return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int tempCur = inStart;
        for ( ; tempCur <= inEnd; ++tempCur) {
            if (inorder[tempCur] == preorder[preStart]) {
                break;
            }
        }
        TreeNode left = buildTree(preorder, preStart + 1, tempCur - inStart + preStart, inorder, inStart, tempCur - 1);
        TreeNode right = buildTree(preorder, tempCur - inStart + preStart + 1, preEnd, inorder, tempCur + 1, inEnd);
        root.left = left;
        root.right = right;
        return root;
    }
}

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return f(preorder,0,preorder.length,inorder,0,preorder.length);
    }
     public TreeNode f(int[] pre,int s,int e,int []mid,int s1,int e1){
        if(s==e) return null;
        TreeNode t = new TreeNode(pre[s]);
        int i=s1;
        for(;i<e1;i++)
            if(mid[i]==pre[s]) break;
        t.left=f(pre,s+1,s+i-s1+1,mid,s1,i);
        t.right=f(pre,s+i-s1+1,e,mid,i+1,e1);
        return t;
    }
}

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null ||preorder.length < 1 || inorder.length < 1)
            return null;
        return getRoot(preorder, inorder, 0, 0, inorder.length-1);
    }
    
    public TreeNode getRoot(int[] preorder, int[] inorder, int preStart, int left, int right) {
        int val = preorder[preStart];
        TreeNode root = new TreeNode(val);
        int i;
        for(i=left; i<=right; i++) {
            if(inorder[i] == val)
                break;
        }
        if(left <= i-1)
        	root.left = getRoot(preorder, inorder, preStart+1, left, i-1);
        if(right >= i+1)
            root.right = getRoot(preorder, inorder, preStart+ i - left +1, i+1, right);
        return root;
    }
}

/*经在leetcode上测试，借助hashmap可以提高不少效率，修改如下*/
import java.util.*;
public class Solution { 
    HashMap<Integer,Integer> in_map = new HashMap<Integer,Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i <preorder.length; i++) 
            in_map.put(inorder[i],i);//借助hashmap存储元素在中序遍历中的下标
    	return helper(0, 0, inorder.length - 1, preorder, inorder);
}

    public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = in_map.get(root.val); // 获取该根结点在中序遍历中的下标
        root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
        root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
        return root;
    }
}

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
     public static TreeNode buildTree(int[] preorder, int[] inorder) {
            if(inorder==null||preorder==null||inorder.length==0||preorder.length==0||preorder.length!=inorder.length){
                return null;
            }         
             return buildTree(inorder,0,inorder.length-1, preorder,0,preorder.length-1);
         }
        private static TreeNode buildTree(int[] inorder, int instart, int inend, int[] preorder, int prestart,
                int preend) {
             if (instart>inend||prestart>preend) {
                    return null;
                }
            TreeNode root = new TreeNode(preorder[prestart]);
            for(int i=0;i<inorder.length;i++){
                if(inorder[i]==preorder[prestart]){
                    root.left = buildTree(inorder, instart, i-1, preorder, prestart+1,
                            prestart+i-instart);

                    root.right = buildTree(inorder, i+1, inend, preorder, prestart+i-instart+1,
                            preend);
                }
            }            
            return root;                    
        }
}

public TreeNode buildTree(int[] preorder, int[] inorder) { return helper(0, 0, inorder.length - 1, preorder, inorder);
} public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) { if (preStart > preorder.length - 1 || inStart > inEnd) { return null;
    }
    TreeNode root = new TreeNode(preorder[preStart]); int inIndex = 0; // Index of current root in inorder for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == root.val) {
            inIndex = i;
        }
    }
    root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
    root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder); return root;
}

public class Solution {
    	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return createBinaryTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
	}

	public TreeNode createBinaryTree(int[] preorder, int preLeft, int preRight, int[] inorder, int orderLeft, int orderRight) {
		if(preLeft > preRight || orderLeft > orderRight) return null;
		TreeNode root = new TreeNode(preorder[preLeft]);
		int len = 0;
		for (int i = orderLeft; i <= orderRight; i ++) {
			if(inorder[i] == preorder[preLeft]) break;
			len ++;
		}
		root.left = createBinaryTree(preorder, preLeft + 1, preLeft + len, inorder, orderLeft, orderLeft + len - 1);
		root.right = createBinaryTree(preorder, preLeft + len + 1, preRight, inorder, orderLeft + len + 1, orderRight);
		return root;
	}
}