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:

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

    Example 2:

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

    题意

    将树从根节点到叶结点路径上的所有数字组合成一个整数，求所有这样的整数的和。

    思路

    典型的回溯法。

    代码实现 - 递归 1

    1. class Solution {
    2.     int sum = 0;
    4.     public int sumNumbers(TreeNode root) {
    5.         if (root != null) {
    6.             dfs(root, 0);
    7.         }
    9.         return sum;
    10.     }
    12.     private void dfs(TreeNode x, int cur) {
    13.         if (x.left == null && x.right == null) {
    14.             sum += cur * 10 + x.val;
    15.             return;
    16.         }
    18.         if (x.left != null) {
    19.             dfs(x.left, cur * 10 + x.val);
    20.         }
    21.         if (x.right != null) {
    22.             dfs(x.right, cur * 10 + x.val);
    23.         }
    24.     }
    25. }

    代码实现 - 递归 2

    1. class Solution {
    2.     public int sumNumbers(TreeNode root) {
    3.         return dfs(root, 0);
    4.     }
    6.     private int dfs(TreeNode x, int sum) {
    7.         if (x == null) {
    8.             return 0;
    9.         }
    11.         sum = sum * 10 + x.val;
    13.         if (x.left == null && x.right == null) {
    14.             return sum;
    15.         }
    17.         return dfs(x.left, sum) + dfs(x.right, sum);
    18.     }
    19. }