LeedCode刷题：129.求根到叶子节点数字的之和

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

解题思路：dfs深度优先遍历搜索，本质是搜索叶子结点，边搜索边更新tmp的值——不是叶子结点就将tmp*10+此点的val继续向下搜索，直至找到叶子结点，当前root节点的左右孩子为同时为空，即为叶子节点时，是dfs出口。就将此tmp加入sum当中，最终返回sum的值

代码：

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10  /* 此题本质是寻找叶子结点，并将tmp加入sum中，最终搜索完全部的叶子结点，返回sum */
11 class Solution {
12     static int sum;
13     public int sumNumbers(TreeNode root) {
14         sum=0;
15         dfs(root,0);//从根节点开始寻找，val初始为0
16         return sum;
17     }
18     public static void dfs(TreeNode root,int val){
19         if(root==null)return ;//节点为空，回溯
20         int tmp=val*10+root.val;//存储暂时值，碰到叶子结点了，就将此值加入sum
21         if(root.left==null&&root.right==null){//是叶子结点时才sum加和
22             sum+=tmp;
23         }
24         dfs(root.left,tmp);//不是叶子结点则继续寻找至叶子结点
25         dfs(root.right,tmp);
26     }
27 }