C++ code ,Time Limit Exceeded ! How to improve it ?


  • 0
    D
    class Solution {
    public:
        TreeNode *sortedArrayToBST(vector<int> &num) 
    	{
    		TreeNode* root = NULL;
    		for(int i=0; i<num.size(); ++i)
    			Insert(root,num[i]);
    		return root;
        }
    	void Insert(TreeNode* &root, int x)
    	{
    		if(root == NULL)
    		{
    			root = new TreeNode(x);
    			return ;
    		}
    		if(x > root->val)
    		{
    			Insert(root->right,x);
    			if(2 == Height(root->right) - Height(root->left))
    			{
    				SingleRotateRight(root);
    			}
    		}
    	}
    	void SingleRotateRight(TreeNode* &k2)
    	{
    		TreeNode* k1 = k2->right; 
    		k2->right = k1->left;
    		k1->left = k2;
    		k2 = k1;
    	}
    	int Height(TreeNode* root)
    	{
    		if(root == NULL)
    			return 0;
    		else
    		{
    			int l = Height(root->left);
    			int r = Height(root->right);
    			return (l>r ? l : r) + 1;
    		}
    	}
    };

  • 1
    L

    Your solution looks to be n lg n (actually greater than this because you are getting the height of the tree multiple times as well so its something like n (lg n)^2)because you are inserting new nodes from the root (which takes lg n time) for every element n. You can simply do this in n time by using a variation of binary search. You know the array is sorted. This means that the middle element will be the root. Then recursively assemble it. The middle element of the left sub array is going to be the left node, and the middle element of the right sub array is going to be the right node, etc.


Log in to reply
 

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