# Java Solution DFS in recursive way and iterative way, BFS in iterative way

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
// DFS recursive, this solution is straightly understandable.
public class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode root, int sum) {
if (root == null) return 0;
int newSum = root.val + sum * 10;
if (root.left == null && root.right == null) return newSum;
return dfs(root.left, newSum) + dfs(root.right, newSum);
}
}
//Whatever iterative DFS or BFS, the point is to recode the sum of parent nodes so far.
// DFS iterative
public class Solution {
public int sumNumbers(TreeNode root) {
if (root == null) return 0;
Stack<TreeNode> remain = new Stack<>();
remain.push(root);
int sum = 0;
TreeNode travel = root;
while(!remain.isEmpty()) {
travel = remain.pop();
if (travel.right != null) {
travel.right.val = travel.right.val + travel.val * 10;
remain.push(travel.right);
}
if (travel.left != null) {
travel.left.val = travel.left.val + travel.val * 10;
remain.push(travel.left);
}
if (travel.left == null && travel.right == null) {
sum += travel.val;
}
}
return sum;
}
}
// BFS iterative
public class Solution {
public int sumNumbers(TreeNode root) {
if (root == null) return 0;
int sum = 0;
TreeNode travel = null;
remain.offer(root);
while(!remain.isEmpty()) {
travel = remain.poll();
if (travel.left != null) {
travel.left.val = travel.val * 10 + travel.left.val;
remain.offer(travel.left);
}
if (travel.right != null) {
travel.right.val = travel.val * 10 + travel.right.val;
remain.offer(travel.right);
}
if (travel.left == null && travel.right == null) sum += travel.val;
}
return sum;
}
}
``````

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