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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param inorder int整型一维数组
     * @param postorder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode buildTree (int[] inorder, int[] postorder) {
        // write code here

        //e []  arr = Arrays.copyOfrange(arr,from,to);
        //注意一下to并不包含
        //递归出口
        if (inorder.length == 0) return null;

        //在后序遍历序列寻找当前Tree的根节点，并建立当前树根
        int postRight = postorder.length - 1;
        TreeNode root  = new TreeNode(postorder[postRight]);
        //根据树根和中序序列，寻找到左子树和右子树
        int indexRoot = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == postorder[postRight]) {
                indexRoot = i;
                break;
            }
        }
        int [] newLeftPostorder = Arrays.copyOfRange(postorder,0,indexRoot);
        int [] newLeftInorder = Arrays.copyOfRange(inorder,0,indexRoot);
        int [] newRightInorder = Arrays.copyOfRange(inorder,indexRoot+1,postRight+1);
        int [] newRightPostorder = Arrays.copyOfRange(postorder,indexRoot,postRight);  
        //递归建立左右子树的根节点（也就是当前树根的左右孩子）
        root.left = buildTree (newLeftInorder, newLeftPostorder);
        root.right = buildTree (newRightInorder, newRightPostorder);
        return root;   
    }

}

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

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

**/

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

private TreeNode build(int[] inorder,int ileft,int iright, int[] postorder, int pleft, int pright) {
if (pleft>pright||ileft>iright)
return null;
int rootVal=postorder[pright];
TreeNode root = new TreeNode(rootVal);
int rootIndex = findRoot(inorder, postorder, ileft,iright,rootVal);
root.left=build(inorder,ileft,rootIndex-1,postorder,pleft,pleft+rootIndex-ileft-1);
root.right=build(inorder,rootIndex+1,iright,postorder,pleft+rootIndex-ileft,pright-1);
return root;
}

//寻找根结点在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 class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0 || postorder == null || postorder.length == 0)
            return null;

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

    }

    public TreeNode build(int[] inorder, int[] postorder, int instart, int inend, int poststart, int postend) {
        if (instart > inend || poststart > postend)
            return null;
        int rootValue = postorder[postend];
        TreeNode root = new TreeNode(rootValue);
        int indexOfRoot = -1;
        for (int i = instart; i <= inend; i++) {
            if (inorder[i] == rootValue) {
                indexOfRoot = i;
                break;
            }
        }

        root.left = build(inorder,postorder,instart,indexOfRoot - 1, poststart, poststart + indexOfRoot - instart - 1);
        root.right = build(inorder,postorder,indexOfRoot+1,inend,poststart + indexOfRoot - instart, postend-1);

        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[] inorder, int[] postorder) {
        if (inorder.length == 0)
            return null;
        return buildTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }
    public TreeNode buildTree(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd)
            return null;
        TreeNode root = new TreeNode(postorder[postEnd]);
        int i = inStart;
        for (i = inStart; i <= inEnd; ++i) {
            if (inorder[i] == postorder[postEnd])
                break;
        }
        TreeNode leftNode = buildTree(inorder, postorder, inStart, i - 1, postStart, postStart + (i - 1) - inStart);
        TreeNode rightNode = buildTree(inorder, postorder, i + 1, inEnd, postStart + (i - 1) - inStart + 1, postEnd - 1);
        root.left = leftNode;
        root.right = rightNode;
        return root;
    }
}

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

import java.util.*;
public class Solution {
    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i=0; i<inorder.length; i++)
            map.put(inorder[i],i);
        return getRoot(inorder, postorder, postorder.length-1, 0, inorder.length-1);
    }
    
    public TreeNode getRoot(int[] inorder, int[] postorder, int postEnd, int left, int right) {
        if(left > right || postEnd < 0)
            return null;
        else {
            int val = postorder[postEnd];
            TreeNode root = new TreeNode(val);
            int index = map.get(val);
            root.left = getRoot(inorder, postorder, postEnd - (right - index + 1), left, index - 1);
            root.right = getRoot(inorder, postorder, postEnd - 1, index + 1, right);
            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[] inorder, int[] postorder) {
		if(inorder==null||postorder==null||inorder.length==0||postorder.length==0||postorder.length!=inorder.length){
			return null;
		}		 
		 return buildTree(inorder,0,inorder.length-1, postorder,0,postorder.length-1);
	 }


	private TreeNode buildTree(int[] inorder, int instart, int inend, int[] postorder, int poststart,
			int postend) {
		 if (instart>inend||poststart>postend) {
	            return null;
	        }
		TreeNode root = new TreeNode(postorder[postend]);
		for(int i=0;i<inorder.length;i++){
			if(inorder[i]==postorder[postend]){
				root.left = buildTree(inorder, instart, i-1, postorder, poststart,
						poststart+i-1-instart);
				
				root.right = buildTree(inorder, i+1, inend, postorder, poststart+i-instart,
						postend-1);
			}
		}
		
		return root;
		
		
	}
}
    

public TreeNode buildTreePostIn(int[] inorder, int[] postorder) { if (inorder == null || postorder == null || inorder.length != postorder.length) return null;
	HashMap<Integer, Integer> hm = new HashMap<Integer,Integer>(); for (int i=0;i<inorder.length;++i)
		hm.put(inorder[i], i); return buildTreePostIn(inorder, 0, inorder.length-1, postorder, 0, 
                          postorder.length-1,hm);
} private TreeNode buildTreePostIn(int[] inorder, int is, int ie, int[] postorder, int ps, int pe, 
                                 HashMap<Integer,Integer> hm){ if (ps>pe || is>ie) return null;
	TreeNode root = new TreeNode(postorder[pe]); int ri = hm.get(postorder[pe]);
	TreeNode leftchild = buildTreePostIn(inorder, is, ri-1, postorder, ps, ps+ri-is-1, hm);
	TreeNode rightchild = buildTreePostIn(inorder,ri+1, ie, postorder, ps+ri-is, pe-1, hm);
	root.left = leftchild;
	root.right = rightchild; return root;
}

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

	public TreeNode createBinaryTree(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
		if(inLeft > inRight || postLeft > postRight) return null;
		TreeNode root = new TreeNode(postorder[postRight]);
		int len = 0;
		for (int i = inLeft; i <= inRight; i ++) {
			if(inorder[i] == postorder[postRight]) break;
			len ++;
		}
		root.left = createBinaryTree(inorder, inLeft, inLeft + len - 1, postorder, postLeft, postLeft + len - 1);
		root.right = createBinaryTree(inorder, inLeft + len + 1, inRight, postorder, postLeft + len, postRight - 1);
		return root;
	}
}