Untitled

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution { //MORRIS
public:
    int sumNumbers(TreeNode* root) {
        TreeNode* cur=root;
        int sum=0,ans=0,depth=0;

        while(cur!=NULL){

            if(cur->left){ //left exist
                TreeNode* pre=cur->left;
                depth=1;
                while(pre->right!=NULL && pre->right!=cur){
                    pre=pre->right;
                    depth++;
                }
                if(pre->right==NULL){ // 
                    pre->right=cur;
                    ans=ans*10 + cur->val;
                    cur=cur->left;
                }else{
                    pre->right=NULL;
                    if(pre->left==NULL) sum+=ans;
                    ans /= pow(10, depth); //does the work of backtracking ,
                    cur=cur->right;
                }

            }else{ // left doesnt exist
                ans=ans*10 +cur->val;
                if(cur->right==NULL) sum+=ans;
                cur=cur->right;
            }
        }
        return sum;
    }
};


/* 
class Solution { // DFS
public:
    int dfs(TreeNode* root,int cur){ //dfs -stack... bfs queue
        if(root==NULL) return 0;
        cur=cur*10 + root->val;
        if(!root->left && !root->right) return cur;//this is the end
        return dfs(root->left,cur) + dfs(root->right,cur);// this is not end , go on recurse
    }

    int sumNumbers(TreeNode* root) {
        return dfs(root,0);      
    }
};


class Solution {
public:
    void rec(TreeNode* root,string p,vector<string>&res){
        if(root==NULL) return;
        p= p + to_string(root->val);
        
        if(root->left==NULL && root->right==NULL){ // necessary condition , otehrwise too many push
            res.push_back(p);
            return;
        }
        
        if(root->left)  rec(root->left ,p ,res);
        if(root->right) rec(root->right,p,res);
    }
    int sumNumbers(TreeNode* root) {
        vector<string> res;
        rec(root,"",res);
        int ans=0;
        for(auto i:res){
            ans+=stoi(i);
        }
        return ans;
    }
};  */