129_Sum_root_to_leaf_numbers

// https://leetcode.com/problems/sum-root-to-leaf-numbers/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
// DFS APPROACH
class Solution {
    public int sumNumbers(TreeNode root) {
        return sum(root, 0);
    }
    public int sum(TreeNode root, int s) {
        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return s * 10 + root.val;
        
        return sum(root.left, s * 10 + root.val) + sum(root.right, s * 10 + root.val);
    }
}


// BFS APPROACH
// class Solution {
//     public int sumNumbers(TreeNode root) {
//         if (root == null)
//             return 0;
//         Queue<TreeNode> queue = new LinkedList();
//         queue.add(root);
//         int total = 0;
//         while (!queue.isEmpty()) {
//             int size = queue.size();
//             while (size > 0) {
//                 TreeNode node = queue.poll();
//                 if (node.left == null && node.right == null)
//                     total += node.val;
//                 if (node.left != null) {
//                     node.left.val = node.val * 10 + node.left.val;
//                     queue.add(node.left);   
//                 }
//                 if (node.right != null) {
//                     node.right.val = node.val * 10 + node.right.val;
//                     queue.add(node.right);   
//                 }
//                 size --;
//             }
//         }
//         return total;
//     }
// }