Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
public class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { // Start typing your Java solution below // DO NOT write main() function HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int i = 0 ; i < inorder.length ; i++){ map.put(inorder[i],i);} return buildtree(map,inorder,0,inorder.length - 1, postorder,0,postorder.length -1); } public TreeNode buildtree(HashMap<Integer, Integer> map,int[] inorder,int start1,int end1, int[] postorder, int start2,int end2){ if(start1 > end1 || start2 > end2){ return null; } TreeNode root = new TreeNode(postorder[end2]); int i = map.get(postorder[end2]); root.left = buildtree(map,inorder,start1,i - 1, postorder,start2,start2+i-1-start1);//
//i-start+1的含义是左子树的大小啊 当然不能乱改了 start2+ i-(start1 +1)
root.right = buildtree(map,inorder,i + 1,end1,postorder,end2-end1+i,end2-1);//rightsub-tree range is end2 -(end1 - i) return root; } }
public class Solution { public TreeNode buildTree( int[] inorder, int[] postorder) { // Start typing your Java solution below // DO NOT write main() function int posLength = postorder.length; int inLength = inorder.length; return buildTree( inorder, 0, inLength-1, postorder,0,posLength-1); } public TreeNode buildTree( int[] in, int inStart, int inEnd,int[] pos, int posStart, int posEnd){ if(inStart > inEnd){ return null; } int rootVal = pos[posEnd]; int rootIndex = 0; for(int i = inStart; i <= inEnd; i++){ if(in[i] == rootVal){ rootIndex = i; break; } } int len = rootIndex - inStart; TreeNode root = new TreeNode(rootVal); root.left = buildTree(in, inStart, rootIndex-1,pos,posStart,posStart+len-1); root.right = buildTree( in, rootIndex+1, inEnd,pos,posStart+len,posEnd-1); return root; } }