129 Sum Root to Leaf Numbers

129. Sum Root to Leaf Numbers

1. Question

Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path1->2->3which represents the number123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path1->2represents the number12. The root-to-leaf path1->3represents the number13.

Return the sum = 12 + 13 =25.

2. Implementation

(1) DFS recursion

class Solution {
    public int sumNumbers(TreeNode root) {
        return findSum(root, 0);
    }

    public int findSum(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }

        sum = 10 * sum + node.val;
        if (node.left == null && node.right == null) {
            return sum;
        }

        return findSum(node.left, sum) + findSum(node.right, sum);
    }
}

(2) BFS

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int res = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> sum = new LinkedList<>();
        queue.add(root);
        sum.add(root.val);

        while (!queue.isEmpty()) {
            TreeNode curNode = queue.remove();
            int curSum = sum.remove();

            if (curNode.left == null && curNode.right == null) {
                res += curSum;
            }

            if (curNode.left != null) {
                queue.add(curNode.left);
                sum.add(10 * curSum + curNode.left.val);
            }

            if (curNode.right != null) {
                queue.add(curNode.right);
                sum.add(10 * curSum + curNode.right.val);
            }
        }
        return res;
    }
}

3. Time & Space Complexity

DFS recursion: 时间复杂度: O(n), 空间复杂度: O(n)

BFS: 时间复杂度: O(n), 空间复杂度: O(w), w是树里有最多node的一层的node个数