Untitled
plain_text
a month ago
2.4 kB
1
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; } }; */