My accepted solution in Java


  • 0
    A
    The key of my solution is to find root 、left 、right every time, and there positions in preorder and inorder .
    
    pMid、iMid: the boundary of left and right
    
    for example
    
    index:        0 1 2 3 4 5  
    preorder:     A B D E C F
    inorder:      D B E A C F     
    
        
    first:
        pStart=0;  pMid=3;  pEnd=5;  iStart=0;  iMid=3;  iEnd=5;   
        root is : A    left tree is: B,D,E  right tree is: C F
        root.left=build(preorder,inorder,pStart+1,pMid,iStart,iMid);
        root.right=build(preorder,inorder,pMid+1,pEnd,iMid+1,iEnd);
    then do similar operation every time , until meet child node.
    
    
    public class Solution {
    
    public TreeNode build(int[] preorder, int[] inorder,int pStart,int pEnd,int iStart,int iEnd)
    {
        if(pStart>pEnd) return null;
        if(pStart==pEnd) return new TreeNode(preorder[pStart]);
        int target=preorder[pStart];
        TreeNode root=new TreeNode(target);
        int pMid=-1,iMid=-1;
        int nums=0;
        for(int i=iStart;i<=iEnd;i++)
        {
            if(inorder[i]==target)
            {
                pMid=pStart+nums;
                iMid=i;
                break;
            }
            nums++;
        }
        root.left=build(preorder,inorder,pStart+1,pMid,iStart,iMid);
        root.right=build(preorder,inorder,pMid+1,pEnd,iMid+1,iEnd);
        return root;
    }
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0) return null;
        if(preorder.length==1) return new TreeNode(preorder[0]);
        
        int target=preorder[0];
        TreeNode root=new TreeNode(target);
        int pStart=0,pMid=0,pEnd=preorder.length-1,iStart=0,iMid=0,iEnd=inorder.length-1;
        int nums=0;
        for(int i=iStart;i<=iEnd;i++)
        {
            if(inorder[i]==target)
            {
                pMid=pStart+nums;
                iMid=i;
                break;
            }
            nums++;
        }
        root.left=build(preorder,inorder,pStart+1,pMid,iStart,iMid);
        root.right=build(preorder,inorder,pMid+1,pEnd,iMid+1,iEnd);
        return root;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.