1717 Return the sum = 12 + 13 = 25.
1818
1919 Solution: 1. Recursion (add to sum when reaching the leaf).
20- 2. Iterative solution.
2120 */
2221
22+
2323/**
2424 * Definition for binary tree
25- *struct TreeNode {
25+ *public class TreeNode {
2626 * int val;
27- * TreeNode* left;
28- * TreeNode* right;
29- * TreeNode(int x): val(x), left(NULL), right(NULL) { }
30- * };
27+ * TreeNode left;
28+ * TreeNode right;
29+ * TreeNode(int x){ val = x; }
30+ * }
3131 */
32- class Solution {
33- public :
34- int sumNumbers (TreeNode *root ) {
35- return sumNumbers_1 (root );
36- }
37-
38- int sumNumbers_1 (TreeNode *root ) {
39- int sum =0 ;
40- sumNumbersRe (root ,0 ,sum );
41- return sum ;
42- }
43-
44- void sumNumbersRe (TreeNode *node ,int num ,int &sum ) {
45- if (!node )return ;
46- num =num *10 +node ->val ;
47- if (!node ->left && !node ->right ) {
48- sum +=num ;
49- return ;
50- }
51- sumNumbersRe (node ->left ,num ,sum );
52- sumNumbersRe (node ->right ,num ,sum );
32+ public class Solution {
33+ public int sumNumbers (TreeNode root ) {
34+ if (root ==null )return 0 ;
35+ return sumNumbersRe (root ,0 );
5336 }
54-
55- int sumNumbers_2 (TreeNode *root ) {
56- if (!root )return 0 ;
57- int res =0 ;
58- queue <pair <TreeNode *,int >>q ;
59- q .push (make_pair (root ,0 ));
60- while (!q .empty ())
61- {
62- TreeNode *node =q .front ().first ;
63- int sum =q .front ().second *10 +node ->val ;
64- q .pop ();
65- if (!node ->left && !node ->right )
66- {
67- res +=sum ;
68- continue ;
69- }
70- if (node ->left )
71- q .push (make_pair (node ->left ,sum ));
72- if (node ->right )
73- q .push (make_pair (node ->right ,sum ));
74- }
75- return res ;
37+ public int sumNumbersRe (TreeNode root ,int last ) {
38+ if (root ==null )return 0 ;
39+ int res =last *10 +root .val ;
40+ if (root .left ==null &&root .right ==null )return res ;
41+ if (root .left ==null )return sumNumbersRe (root .right ,res );
42+ if (root .right ==null )return sumNumbersRe (root .left ,res );
43+ return sumNumbersRe (root .left ,res ) +sumNumbersRe (root .right ,res );
7644 }
77- };
45+ }
