Recursive solution in 4ms C++ w/ explanation


  • 0
    A
    class Solution {
    public:
        void gatherPath(TreeNode* root, vector<vector<int> >&res, vector<int> vec){
            vec.push_back(root->val); //push this node
            if(!root->left && !root->right){ //if this is leaf then push the vector formed so far to result
                res.push_back(vec);
                return;
            }
            //recurse through left and right
            if(root->left) gatherPath(root->left,res,vec);
            if(root->right) gatherPath(root->right,res,vec);
        }
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> op; //return variable
            vector<vector<int> > res; //for gathering paths
            vector<int> vec;
            if(root==NULL) {return {};} // handling special case
            gatherPath(root,res,vec); //recursive function to gather all paths
            //transforming the integer vector to the "pretty print" string
            for(int i=0;i<res.size();i++){
                string s;
                for(int j=0;j<res[i].size();j++){
                    s += to_string(res[i][j]) + "->";
                }
                s.erase(s.length()-2); //to delete off the hanging redundant "->"
                op.push_back(s);
            }
            return op;
        }
    };

Log in to reply
 

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