DFS method, using two stacks, for TreeNode and the path sum

• ``````class Solution {
public:
int sumNumbers(TreeNode* root) {
if(!root)
return 0;
stack<TreeNode*> s1;
stack<int> s2;
s1.push(root);
s2.push(root->val);
int sum=0,ret=0;
while(!s1.empty()){
TreeNode* node=s1.top();
s1.pop();
sum=s2.top();
s2.pop();
if(!node->left&&!node->right){
ret+=sum;
}
if(node->right){
s1.push(node->right);
s2.push(node->right->val + 10*sum);
}
if(node->left){
s1.push(node->left);
s2.push(node->left->val + 10*sum);
}
}
return ret;
}
};

``````

• this is actually BFS, not DFS
similar idea, it really doesn't matter whether we're using stack or queue

``````public class Solution {
public int sumNumbers(TreeNode root){
if(root==null) return 0;
sum.offer(root.val);
queue.offer(root);
int res = 0;
while(!queue.isEmpty()){
TreeNode cur = queue.poll();
int curVal = sum.poll();
if(cur.left==null && cur.right==null){
res += curVal;
continue;
}
if(cur.left!=null){
queue.offer(cur.left);
sum.offer(curVal*10+cur.left.val);
}
if(cur.right!=null){
queue.offer(cur.right);
sum.offer(curVal*10+cur.right.val);
}
}
return res;
}
}
``````

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