129. Sum Root to Leaf Numbers

Leetcode Tree Depth-first Search

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

An example is the root-to-leaf path 1->2->3 which represents the number 123.

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

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

分析

这道题目和LeetCode 113. Path Sum II非常像。在Q113中，给出路径：路径开始于根节点，终止于叶子节点，并且路径的和为给定值。这里要求的是所有路径的和。总体方法其实一样的。

private int sum;
public int sumNumbers(TreeNode root) {
    sum = 0;
    sumNumbersHelper(root, "");
    return sum;
}

private void sumNumbersHelper(TreeNode root, String s) {
    if (root == null) return;
    String sNew = s + Integer.toString(root.val);
    // leaf node
    if (root.left == null && root.right == null) {
        sum += Integer.parseInt(sNew);
        return;
    }
    sumNumbersHelper(root.left, sNew);
    sumNumbersHelper(root.right, sNew);
}

使用StringBuilder，并使用backtracking的思想，删除已访问过的数字：

private int sum;
public int sumNumbers(TreeNode root) {
    sum = 0;
    sumNumbersHelper(root, new StringBuilder());
    return sum;
}

private void sumNumbersHelper(TreeNode root, StringBuilder s) {
    if (root == null) return;
    s.append(Integer.toString(root.val));
    // leaf node
    if (root.left == null && root.right == null)
        sum += Integer.parseInt(s.toString());
    sumNumbersHelper(root.left, s);
    sumNumbersHelper(root.right, s);
    s.deleteCharAt(s.length() - 1);
}

但上面的方法都太笨拙了。因为根本不要保存字符串，直接保存数字，大大节省了内存。

public int sumNumbers(TreeNode root) {
    return sumNumbersHelper(root, 0);
}

private int sumNumbersHelper(TreeNode root, int sum) {
    if (root == null) return 0;
    sum = 10*sum + root.val;
    // leaf node
    if (root.left == null && root.right == null)
        return sum;
    return sumNumbersHelper(root.left, sum) +
            sumNumbersHelper(root.right, sum);
}