# Untitled

unknown
plain_text
a year ago
2.4 kB
2
Indexable
Never
/**
* 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;
}
};  */