Top-down & bottom-up recursive solutions in C++


  • 1
    M

    There are two recursive ways to solve this problem.

    1. Top-down:

    Need a helper function with an additional string to save the output of parent nodes.

    • For the non-leaf node, the helper function is recursively called if there are non-empty subtrees.
    • For the leaf node, the helper function pushes the string of one path into the final result.

    Code:

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        if(root) helper(root, ans, "");
        return ans;
    }
    
    void helper(TreeNode* root, vector<string>& ans, string s){
        if(!root->left && !root->right) ans.push_back(s + to_string(root->val));    // leaf
        if(root->left) helper(root->left, ans, s +  to_string(root->val) + "->");   // left subtree
        if(root->right) helper(root->right, ans, s + to_string(root->val) + "->");  // right subtree
    }
    

    Time complexity: O(N)

    2. Bottom-up:

    No need to use a helper function and additional strings. However, the time complexity is higher.

    • For the leaf node, return the vector with root->val.
    • For the non-leaf node, return the vector with (root->val + all possible strings in its subtrees).

    Code:

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        if(root){
            if(!root->left && !root->right)     // leaf
                ans.push_back(to_string(root->val));
            if(root->left){                     // left subtree
                vector<string> Lchild = binaryTreePaths(root->left);
                for(int i=0; i<Lchild.size(); i++){
                    Lchild[i] = to_string(root->val) + "->" + Lchild[i];
                    ans.push_back(Lchild[i]);
                }
            }
            if(root->right){                    // right subtree
                vector<string> Rchild = binaryTreePaths(root->right);
                for(int i=0; i<Rchild.size(); i++){
                    Rchild[i] = to_string(root->val) + "->" + Rchild[i];
                    ans.push_back(Rchild[i]);
                }
            }
        }
        return ans;
    }
    

    Time Complexity: O(N*logN)


Log in to reply
 

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