Given preorder and inorder 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[] preorder, int[] inorder) { if (inorder == null || preorder == null||inorder.length ==0 || preorder.length==0) return null; int len = preorder.length; return buildTree(preorder,inorder,0,len-1,0,len-1); } public TreeNode buildTree(int[] preorder, int[] inorder,int start1,int end1,int start2,int end2){ if (inorder == null || preorder == null||inorder.length ==0 || preorder.length==0||start1>end1||start2>end2) return null; if (start2==end2|| start1==end1){ TreeNode root = new TreeNode(preorder[start1]); return root; }else{ TreeNode root = new TreeNode(preorder[start1]); int pivot = preorder[start1]; int index= start1; for(; index<end1;i++){ if(pivot == inorder[index]) break; } int index = getIndex(inorder,preorder[start1],start2,end2); int offset = index -start2; root.left = buildTree(preorder,inorder,start1+1,start1+offset,start2,start2+offset-1); root.right = buildTree(preorder,inorder,start1+offset+1,end1,start2+offset+1,end2); return root; } } private int getIndex(int[] inorder, int value,int start,int end) { for (int i = start; i <=end; i++) { if (value == inorder[i]) return i; } return -1; } }
public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { // Start typing your Java solution below // DO NOT write main() function int preLength = preorder.length; int inLength = inorder.length; return buildTree(preorder, 0, preLength-1, inorder, 0, inLength-1); } public TreeNode buildTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd){ if(inStart > inEnd){ return null; } int rootVal = pre[preStart]; 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(pre, preStart+1, preStart+len, in, inStart, rootIndex-1); root.right = buildTree(pre, preStart+len+1, preEnd, in, rootIndex+1, inEnd); return root; } }