C++ 3ms dynamic+recursive way to avoid copy new string in every path


  • 0

    The path to the first hit is following a pre-order traverse.
    After that we just have to pop the last leaf in the post-order.
    Then adding new leaf in pre-order way until the end of full traverse.

    class Solution {
        string path;
        list<int> strLen;
        vector<string> pathStr;
        void traverse(TreeNode* node) {
            if ( !node ) return;
            
            string tmp = path.empty() ? to_string(node->val) : "->"+to_string(node->val);
            path+=tmp;
            strLen.push_back(tmp.size());
            
            traverse(node->left);
            traverse(node->right);
            
            if(!node->left && !node->right) pathStr.push_back(path);
            int flag = 1;
            for( int i=0; i<strLen.back() ; i++ ) path.pop_back();
            strLen.pop_back();
        }
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            path = "";
            traverse(root);
            return pathStr;
        }
    };
    

Log in to reply
 

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