Any better c++ solution than this one (recursive and iterative) -- 4ms ?


  • 1
    M

    Recursive solution:

    class Solution {
    public:
        void helper(TreeNode *root, string p, vector<string> &res){
            if(!root) return;
    
            if(!root->left && !root->right) {
               p += to_string(root->val);
               res.push_back(p);
               return;
            }   
    
            helper(root->left, p + to_string(root->val) + "->", res);
            helper(root->right, p + to_string(root->val) + "->", res);
        }
    
        vector<string> binaryTreePaths(TreeNode* root) {
            string p = "";
            vector<string> res;
            helper(root, p, res);
            return res;
        }
    };
    

    Iterative solution:

    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> res;
            if(!root) return res;
            stack<TreeNode*> nodes;
            stack<string> strs;
            nodes.push(root);
            strs.push("");
    
            while(!nodes.empty()){
    
                TreeNode *top = nodes.top();
                string cs = strs.top();
                nodes.pop();strs.pop();
    
                if(!top->left && !top->right){
                    cs += to_string(top->val);
                    res.push_back(cs);
                }
                else
                {
                    if(top->right) {
                        nodes.push(top->right);
                        strs.push(cs + to_string(top->val) + "->");
                    }
                    if(top->left) {
                        nodes.push(top->left);
                        strs.push(cs + to_string(top->val) + "->");
                    }
                }
            }
    
            return res;
        }
    };

  • 0
    G

    you may substitute the two stacks for only one stack<pair<int, string>> ,which is more clear


Log in to reply
 

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