my O(n) solution which has similar format with Question.105


  • 0
    C

    my O(n) solution which has similar format with Question.105
    '''

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(postorder.length-1, 0, inorder.length-1, inorder, postorder);
    }
    private TreeNode helper(int poEnd, int inStart, int inEnd, int[] inorder, int[] postorder ){
        if(poEnd<0 || inStart>inEnd) return null;
        
        int inIndex=0;
        TreeNode root=new TreeNode(postorder[poEnd]);
        for(int i=inStart; i<=inEnd; i++){
            if(inorder[i]==root.val) inIndex=i;
        }
        
        root.left=helper(poEnd-inEnd+inIndex-1, inStart, inIndex-1, inorder, postorder);
        root.right=helper(poEnd-1, inIndex+1, inEnd, inorder, postorder);
        return root;
    }
    

    '''


Log in to reply
 

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