C++ simple 4ms recursive solution


  • 64
    J
    void binaryTreePaths(vector<string>& result, TreeNode* root, string t) {
        if(!root->left && !root->right) {
            result.push_back(t);
            return;
        }
    
        if(root->left) binaryTreePaths(result, root->left, t + "->" + to_string(root->left->val));
        if(root->right) binaryTreePaths(result, root->right, t + "->" + to_string(root->right->val));
    }
    
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        if(!root) return result;
        
        binaryTreePaths(result, root, to_string(root->val));
        return result;
    }

  • 1

    Nice solution!
    From your solution I have learnt about function of to_string and + in 'string' container.
    Thank you very much.


  • 1
    S

    great solution. I shared the same idea with yours. But my solution showed run rime error, can anyone tell me the reason?

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
    	std::vector<string> rootPaths(TreeNode* root, string str, std::vector<string> res) {
    		if(!root->left && !root->right) {
    			res.push_back(str);
    			return res;
    		}
    		if(root->left) {
    			res = rootPaths(root->left, str + "->" + to_string(root->left->val), res);
    		}
    		if(root->right) {
    			res = rootPaths(root->right, str + "->" + to_string(root->right->val), res);
    		}
    	}
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
        	std::vector<string> res;
            if(!root) {
            	return res;
            }
            res = rootPaths(root, to_string(root->val), res);
            return res;
        }
    };

  • 0
    P

    Hey, you should also return the res after the calls for root->left and root->right. untill then the rsult is not returned back to the main calling function i.e. binary tree paths.


  • 1
    Z

    Really great solutions. I'd like to share my solution while pass string reference and use string like a stack, so it no longer need to keep so many string as it's a recursion process.

    Hope to see your comments!

    And may I ask how c++ really do with string erase and append? Will it always create a new string and delete the old one?

    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> res;
            if(!root) return res;
            
            string save=to_string(root->val);
            DFS(root,res,save);
            
        }
        
        void DFS(TreeNode* root,vector<string>& res, string& save){
            if(!(root->left) && !(root->right)) {       //leaf
                res.push_back(save);
                return;
            }
            else{
                
                if(root->left) {
                    save+="->"+to_string(root->left->val);
                    DFS(root->left,res,save);
                    size_t found = save.rfind("->");
                    save.erase(found,save.size()-found);
                }
                if(root->right){
                    save+="->"+to_string(root->right->val);
                    DFS(root->right,res,save);
                    size_t found = save.rfind("->");
                    save.erase(found,save.size()-found);
                }
                return;
            }
        } 
    };

  • 0
    P

    recursion is magic...


  • 0
    S

    is there a way to avoid copying the strings for each recurisve call?


  • 0
    K

    great solution. From this solution I got function to_string fuinction. One minute I use stringstream!!!! using to_string helps save solution from 6ms to 3ms


Log in to reply
 

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