Concise C++ 4ms solution, one pass, O(log N) extra space except for the result


  • 0
    X
    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> result;
            vector<int> currentPath;
            size_t currentIndex = 0;
            binaryTreePathsRecursive(root, result, currentPath, currentIndex);
            return result;
        }
        
        void binaryTreePathsRecursive(const TreeNode* root, vector<string>& paths, vector<int>& currentPath, size_t currentIndex)
        {
            if(root == NULL) return;
            
            if(currentIndex + 1 > currentPath.size()) currentPath.push_back(root->val);
            else currentPath[currentIndex] = root->val;
            ++currentIndex;
            
            if(root->left == NULL && root->right == NULL) // leaf found - add the current path
            {
                ostringstream oss;
                for(size_t i = 0; i < currentIndex - 1; ++i) oss << currentPath[i] << "->";
                oss << currentPath[currentIndex - 1];
                paths.push_back(oss.str());
                return;
            }
            
            binaryTreePathsRecursive(root->left, paths, currentPath, currentIndex);
            binaryTreePathsRecursive(root->right, paths, currentPath, currentIndex);
        }
    };

  • 0

    Seems pretty clearly not O(log N) but O(N) additional space (assuming N is the number of nodes).


Log in to reply
 

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