129. Sum Root to Leaf Numbers --M

Q:
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.
A:    
Note:   A leaf node has no children.
思路不是很清晰，先用一个最简单的方法。实现了，看看有什么问题需要注意的吧。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int res = 0;
        if(root)
            helper(root, 0, res);
        return res;
    }
private:
    void helper(TreeNode* root, int preSum, int & res){
        int curSum =  preSum * 10 + root->val;
        if(!root->left && !root->right)
            res += curSum;
        else{
            if(root->left)
                helper(root->left, curSum, res);
            if(root->right)
                helper(root->right, curSum, res);
        }
    }
};

----------------------------因此我们分别计算左右子树，再加起来，就accept了--------------------

public class Solution {
      public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getSum(root,  0);
    }

    private int getSum(TreeNode node,  int curSum) {
        // return the new sum of the of the current
        if (node.left == null && node.right == null) {// find leaf
            return  (node.val + curSum * 10);            
        }
        int sumLeft =0, sumRight =0;
        if (node.left != null) { // go further left
            sumLeft = getSum(node.left,  curSum * 10 + node.val);
        }
        if (node.right != null) {// go further left
            sumRight = getSum(node.right, curSum * 10 + node.val);
        }
        return sumLeft + sumRight;
    }
}

Mistakes:
1 :  思路不清晰。   刚开始走了弯路， 去生成新的tree去了。其实是不需要新的tree的。
当然，也可以在getSum（）方法中，传递一个 preSum 参数，来记录前序节点的和。


Learned:
leetcode 中，添加了新的类变量，会导致一系列问题。
 见买买提链接

use a data member.
and the result are accumulated...

I think your algorithm is right. But you use static vars, which might cause problem. Because maybe OJ just creates one instance of class solution, and uses it on many test cases. So you had better reset them. This is the only reason I can come up with. I am not sure. You can use a vector to track the node instead.
 ---------------1337
yes. that's the problem.
and i initialized it to 0 in the function and here we go.

【 在 stupidrobot (robot) 的大作中提到: 】
: 谨慎估计你添加新的类变量了

下面的解法，是不对的。Tiger 自己想想，是哪里不对了。

public class SumRootToLeafNumbers2 {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getSum(root, 0, 0);
    }

    private int getSum(TreeNode node, int totalSum, int curSum) {
        // return the new sum of the of the current
        if (node.left == null && node.right == null) {// find leaf
            totalSum += (node.val + curSum * 10);
            return totalSum;
        }
        if (node.left != null) { // go further left
            totalSum += getSum(node.left, totalSum,curSum * 10 + node.val);
        }
        if (node.right != null) {
            totalSum += getSum(node.right,totalSum, curSum * 10 + node.val);
        }
        return totalSum;
    }
}

答案就在于，左右子树的结果，不应该是 totalSum +=   ， 而仅仅 totalSum= 就可以了。