Is there any O(1) solution for this question?


  • 0
    R

    Hi, I solved the question with the normal recursive code, I wonder if we could have the solution with O(1) space? I wonder if we could solve it with morris traversal ... to get to the O(1) solution?

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

Log in to reply
 

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