2012年10月21日星期日

Construct Binary Tree from Preorder and Inorder Traversal

public TreeNode buildTree(int[] preorder, int[] inorder) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(preorder == null|| preorder.length==0 || inorder == null) return null;
        int l1 =0;
        int l2 =0;
        int h1=preorder.length-1;
        int h2=inorder.length-1;
        return buildTreeT(preorder, l1, h1, inorder,l2, h2);
    }
   
    public TreeNode buildTreeT(int[] preorder, int l1, int h1, int[] inorder, int l2, int h2){
       
        int index1=0;
        int index2=0;
        if(l1>h1||l2>h2) return null;       
       
        for(int i =l2; i<=h2;i++){
            if(inorder[i] == preorder[l1]){
                index2=i;
            }
        }
       
        index1 = index2-l2+l1;
       
        TreeNode head = new TreeNode(preorder[l1]);
        head.left=buildTreeT(preorder, l1+1, index1, inorder, l2,index2-1);
        head.right=buildTreeT(preorder, index1+1, h1, inorder,index2+1,h2);
        return head;
    }

没有评论: