Work Around Bugs

Sum Root to Leaf NumbersFeb 191675 / 4693
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.
For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

-----------乌龙的分割线oops..--------------正解随后---------------
我这什么记性啊，看完题目去睡觉，然后睡前想了下，自以为想出来了，今天早上唰唰写好 code, 放到OJ一测试，没过，仔细一看，原来我答非所问，完全做的另外一道题！！为了不浪费劳动成果，还是贴在这把，我做的题是：对每条root-to-leaf path求和，最后得出总和，比如
  1
2  3
得到的就是(1+2)+(1+3) = 7.

void postorder(TreeNode *root, int &sum, unordered_map<TreeNode *, int> &count){
   if(!root) return;
   if(!root->left && !root->right) {
     count[root] = 1;
     sum += root->val;
     return;
  }
   postorder(root->left, sum, count);
   postorder(root->right,sum,count);
   count[root] = 0;
   if(root->left) count[root] +=  count[root->left];
   if(root->right) count[root] += count[root->right];
   sum += root->val * count[root];
  
}

int sumNumbers(TreeNode *root) {
       int sum = 0;
unordered_map<TreeNode *, int> count;
       postorder(root, sum,count);
       
      return sum;
    }

------------------正解my solution-------------------后面有更优解-------------
还好思路也差不多，还更简单，建个map对每个node重新赋值就好了
void preorder(TreeNode *root, int &sum, unordered_map<TreeNode *, int> &num){
   if(!root->left && !root->right) {
     sum += num[root];
     return;
  }

  if(root->left) {
     num[root->left] = num[root] *10 + root->left->val;
     preorder(root->left, sum, num);
  }                  
  if(root->right) {
     num[root->right] = num[root] *10 + root->right->val;
     preorder(root->right, sum, num);
  }
}

int sumNumbers(TreeNode *root) {
      if(!root) return 0;
      int sum = 0;
unordered_map<TreeNode *, int> num;
      num[root] = root->val;
       preorder(root, sum, num);
       
      return sum;
    }
-------------最优解best solution-----------------
写完上面的解后，觉得这个map挺多余的，应该能去掉，但是懒得弄了，于是找了个别人的code(lu-an gong at Leetcode)，就是用一个动态number代替map,每次做到leaf node这个number就回去一个，如果做完右子树再回去一个。

0. int sumNumbers(TreeNode *root) {  
1.     int num = 0, sum = 0;  
2.     sumNumbersImpl(root, num, sum);  
3.     return sum;  
4. }  
5.   
6. void sumNumbersImpl(TreeNode *root, int& num, int& sum) {   
7.     if (root == nullptr) return;   
8.     num = num * 10 + root->val;   
9.     if (root->left == nullptr && root->right == nullptr) {   
10.        sum += num;   
11.     }   
12.     else {   
13.        sumNumbersImpl(root->left, num, sum);   
14.        sumNumbersImpl(root->right, num, sum);   
15.     }   
16.     num /= 10;   
17. }