Time Complexity of Divide and Conquer


  • 0
    N

    Hi, I know this question can be solved by "Divide and Conquer"

    vector<string> binaryTreePaths(TreeNode* root) {
        return treePath(root);
    }
    
    vector<string> treePath(TreeNode* root) {
        //base case
        vector<string> res;
        if (root == nullptr) {
            return res;
        }
    
        if (root->left == nullptr && root->right == nullptr) {
            res.push_back(std::to_string(root->val));
        }
        //divide&conquer
        vector<string>leftTree = treePath(root->left);
        vector<string>rightTree = treePath(root->right);
        //combine
        int leftSize = leftTree.size();
        for(int i = 0; i < leftSize; i++) {
            res.push_back(std::to_string(root->val) + "->" + leftTree[i]);
        }
        
        int rightSize = rightTree.size();
        for(int i = 0; i < rightSize; i++) {
            res.push_back(std::to_string(root->val) + "->" + rightTree[i]);
        }
        
        return res;
    }
    

    My question is what the running time of this solution. I could not figure out the time cost for combine step


Log in to reply
 

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