My recursive java solution


  • 1
    C
    private static int[] inorder;
    private static int[] postorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder==null || inorder.length == 0){
            return null;
        }else if ( inorder.length == 1){
            return new TreeNode(inorder[0]);
        }
        this.inorder = inorder;
        this.postorder = postorder;
        return buildTreeHelper(0,inorder.length-1,0,postorder.length-1);
    }
    
    private TreeNode buildTreeHelper(int inStart, int inEnd, int postStart, int postEnd){
        //base cases
        if(inStart > inEnd || postStart > postEnd){
            return null;
        } else if(inStart == inEnd){
            return new TreeNode(inorder[inStart]);
        }
        TreeNode root = new TreeNode(postorder[postEnd]);
        int inRootIdx=-1;
        for(int i = inStart; i <= inEnd; ++i){
            if(inorder[i]==postorder[postEnd]){
                inRootIdx = i;
                break;
            }
        }
        root.left = buildTreeHelper(inStart,inRootIdx-1,postStart,postStart+(inRootIdx-1-inStart));
        root.right = buildTreeHelper(inRootIdx+1,inEnd,postStart+(inRootIdx-1-inStart)+1,postEnd-1);
        return root;
    }

Log in to reply
 

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