Clean java dfs solution O(n)


  • 0
    C
    public TreeNode buildTree(int[] inorder, int[] postorder) {
            return buildBST(postorder.length-1, 0, postorder.length-1, inorder, postorder);
        }
        private TreeNode buildBST(int rootPos, int inStart, int inEnd, int[] inorder, int[] postorder){
            if(inStart > inEnd || rootPos < 0) return null;
            int midPos=0;
            for(int i=inStart;i<=inEnd;i++)
                if(postorder[rootPos] == inorder[i]) midPos = i;
            TreeNode node = new TreeNode(postorder[rootPos]);
            node.left = buildBST(rootPos - (inEnd - midPos) - 1, inStart, midPos-1, inorder, postorder);
            node.right = buildBST(rootPos-1, midPos+1, inEnd, inorder, postorder);
            return node;
        }
    

  • 0
    H

    i think i t should be o(logn), because i think it's dividing and conquer logic, right ?


  • 0
    C

    no its O(n), you have to create very node, which is n nodes.


  • -1
    L

    It has a complexity of O(n^2). Search midpos in each step is O(n), while the total number of node to be constructed is n.


  • 0
    C

    @leoloe326 no, it is still O(n), the number of searches is n


  • 0
    L

    @cgxy1995 Yes, my mistake.


Log in to reply
 

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