# 129. Sum Root to Leaf Numbers

Question link is here.

# Question

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

# Solution

Whenever it comes to the problems with traverse through the tree, we can consider using DFS or BFS.

In this situation, we can use bfs search, and use a variable cur to keep track of the root-node sum of the current sum, and whenever we encouter a leaf, we add the sum to result.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        self.res = 0
        def helper(node, cur):
            if node == None:
                return
            if node != None:
                cur = cur * 10 + node.val
            if node.left == None and node.right == None:
                self.res += cur
            if node.left != None:
                helper(node.left, cur)
            if node.right != None:
                helper(node.right, cur)
        helper(root, 0)
        return self.res

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public int res = 0;
    public int sumNumbers(TreeNode root) {
        helper(root, 0);
        return res;
    }
    public void helper(TreeNode node, int cur) {
        if(node == null)
            return;
        cur = cur * 10 + node.val;
        if(node.left == null && node.right == null) {
            res += cur;
            return;
        }
        if(node.left != null) {
            helper(node.left, cur);
        }
        if(node.right != null) {
            helper(node.right, cur);
        }
    }
}

Time complexity: $O(n)$ where n is the number of cells in the board.

Leetcode 129

Sum Root to Leaf Numbers

# 129. Sum Root to Leaf Numbers

# Question

# Solution