/ Data Structure and Algorithms  

Leetcode 129. Sum Root to Leaf Numbers

Question



Given a binary tree, the path from the root node to the leaf node forms a number. Calculates the sum of all numbers.

Similar Question

Solution

We need to traverse the binary tree, and record the sum of the current path during the traversal process. When it comes to traversal, it is nothing more than BFS and DFS. If BFS is performed, we need to maintain the sum of multiple paths during the process, so we choose DFS.

When it comes to DFS, we can use recursion, or use the stack.

When it comes to recursion, we can use both backtracking and divide and conquer.

Let’s look at the backtracking solution.

The idea of backtracking is to keep traversing in depth until a solution is obtained and record the current solution. Then return to the previous state to continue the depth traversal.

So we need to define a function to get this solution.

1
private void dfs(TreeNode node, int tempSum)

This function means that when traversing from the root node to the node, the cumulative sum of the paths is cursum.

Here we use a global variable result to store the sum of each path.

So the exit of backtracking is that when we reach the leaf node, save the current accumulated path sum.

1
2
3
4
if (node.left == null && node.right == null) {
    result += tempSum;
    return;
}

Then just try the left and right subtrees separately.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int result = 0;

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

    dfs(root, root.val);

    return result;
}

private void dfs(TreeNode node, int tempSum) {
    // reach leaf node
    if (node.left == null && node.right == null) {
        result += tempSum;
    }

    // try left tree
    if (node.left != null) {
        dfs(node.left, tempSum * 10 + node.left.val);
    }

    // try right tree
    if (node.right != null) {
        dfs(node.right, tempSum * 10 + node.right.val);
    }
}