题解 | #二叉树根节点到叶子节点的所有路径和#

/*
描述
给定一个仅包含数字\ 0-9 0−9 的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
例如根节点到叶子节点的一条路径是1\to 2\to 31→2→3,那么这条路径就用\ 123 123 来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：
这颗二叉树一共有两条路径，
根节点到叶子节点的路径 1\to 21→2 用数字\ 12 12 代替
根节点到叶子节点的路径 1\to 31→3 用数字\ 13 13 代替
所以答案为\ 12+13=25 12+13=25
Main idea:
前序遍历，储存所有的path，然后使用string将每个path 中的所有值都concat到一个str中，再使用atoi()函数转成数字，加到sum之中即可
*/

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        sum = 0;
        if (root == nullptr) return sum;
        preOrder(root);
        string str;
        for (int i = 0; i < result.size(); ++i) {
            str.clear();
            for (int j = 0; j < result[i].size(); ++j) {
                str += to_string(result[i][j]);
            }
            sum += atoi(str.c_str());
        }
        return sum;
    }

private:
    int sum;
    vector<vector<int> > result;
    vector<int> path;

    void preOrder(TreeNode* root) {
        path.push_back(root->val);
        if (root->left == nullptr && root->right == nullptr) {
            result.push_back(path);
        }
        else {
            if (root->left)
                preOrder(root->left);
            if (root->right)
                preOrder(root->right);
        }
        path.pop_back();
    }
};