class Solution {
void Add_array(TreeNode* root,int current,int &sum){ /*current = the value from top to the current node*/
if(root>left==NULL && root>right==NULL){/*sum is the total sum of roottoleaf numbers*/
sum += current;
return;
}
if(root>left) Add_array(root>left,current*10+root>left>val,sum);
if(root>right) Add_array(root>right,current*10+root>right>val,sum);
return;
}
public:
int sumNumbers(TreeNode* root) {
if(!root) return 0;
int sum = 0;
Add_array(root,root>val,sum);
return sum;
}
};
4ms cpp solution


@PKUGoodSpeed All recursive solutions use extra space, in fact, all recursive soltuions use A LOT of extra space in thread stack.

@ayuanx Yea, I see. I wrote this solution long time ago. If not using recursive, we must use stack for traversal the tree (I think this must to be done in this problem.).