leetcode-129. 求根到叶子节点数字之和

思路：用一个字符串记录节点的值，每次将节点的值添加到字符串的最后，当访问到叶子节点时，将路径和计入sum.

回溯时，弹出最后的一个字符值即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    void search(TreeNode* root, string str, int& sum) {
	 if (root == NULL)
		 return;
//记录非空节点的值
	 str.append(1, '0' + root->val);

	 if (root->left == NULL && root->right == NULL) {//叶子节点
		 sum += atoi(str.c_str());
		 str.erase(str.size()-1, 1);//回溯
		 return;
	 }
	 search(root->left, str, sum);
	 search(root->right, str, sum);
	 return;
 }
public:
    int sumNumbers(TreeNode* root) {
        if(root==NULL)
            return 0;
        int sum=0;
        search(root,"",sum);
        return sum;
    }
};