5-line C++ recursive clean solution 3ms (with explanation)


  • 2

    Key Observation: a path from root r is simply r->val + path from r->left or r->right.

    Algorithm:

    1. Base case of recursion: no paths if root r == NULL.
    2. Get paths of left sub-tree pl and right sub-tree pr by recursion.
    3. Append root value to_string(r->val) + "->" in front of each path in pl, pr to get final collection.
        vector<string> binaryTreePaths(TreeNode* r) {
            if (!r) return {};
            vector<string> pl(binaryTreePaths(r->left)), pr(binaryTreePaths(r->right));
            for (auto& p:pr) pl.push_back(p); // append pr to pl
            for (auto& p:pl) p = to_string(r->val) + "->" + p; // append root value to front
            return pl.size()? pl : vector<string>(1, to_string(r->val));        
        }
    

Log in to reply
 

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