What's the time complexity of my Accepted Java Solution?


  • 1
    W

    I have this Accepted solution but I didn't figure out the time complexity of it. Could anyone help?

    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            
            return findRoot(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
        }
        
        private TreeNode findRoot(int[] inorder, int inleft, int inright, int[] postorder, int postleft, int postright){
            
            if(inleft > inright)return null; // base case
            
            int rootVal = postorder[postright]; // the last node in postorder is always the root node
            TreeNode root = new TreeNode(rootVal);
            
            // find position of the root node in inorder array
            int mid = 0;
            for(int i=inleft; i<=inright; ++i){
                
                if(inorder[i] == rootVal){
                    mid = i;
                    break;
                }
            }
            
            int leftNum = mid - inleft; // number of nodes in left part
            
            root.left = findRoot(inorder, inleft, mid-1, postorder, postleft, postleft+leftNum-1); // left subtree is on the left side of the root
            root.right = findRoot(inorder, mid+1, inright, postorder, postleft+leftNum, postright-1); // right subtree is on the right side of the root
            
            return root;
        }
    }

  • 0
    O

    It is not O(n) for sure. Probably O(n*logn) if the tree is balanced.


  • 0
    C

    I figure out the same algorithm with you!


  • 0
    D

    Your algorithm is O(nlogn) if the binary tree is balanced. Space complexity is the level of stack which is O(logn) if the tree is balanced.


Log in to reply
 

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