BFS solution

  • 0

    Implement a breath first search. At each node, enqueue children of the node and the current value for the number that is formed from root to the current node. When you encounter a leaf, you have reached a valid number from the root to the leaf, add it to the sum. When the queue is empty, all valid numbers are processed.

    class Solution {
        public int sumNumbers(TreeNode root) {
            if(root == null){
                return 0;
            int sum = 0;
            Queue<LevelNode> listNumbers = new LinkedList<LevelNode>();
            listNumbers.offer(new LevelNode(root, root.val));
                LevelNode currentNode = listNumbers.remove();
                TreeNode treeNode = currentNode.treeNode;
                int currentVal = currentNode.currentVal;
                if(treeNode.left != null){
                    int sumToQueue = currentVal * 10 + treeNode.left.val;
                    listNumbers.offer(new LevelNode(treeNode.left, sumToQueue));
                if(treeNode.right != null){
                    int sumToQueue   = currentVal * 10 + treeNode.right.val;
                    listNumbers.offer(new LevelNode(treeNode.right, sumToQueue));
                if(treeNode.left == null && treeNode.right == null){
                    sum += currentVal;
            return sum;
        class LevelNode {
            TreeNode treeNode;
            int currentVal;
            LevelNode(TreeNode treeNode, int currentVal){
                this.treeNode = treeNode;
                this.currentVal = currentVal;

Log in to reply

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