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

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int sumNumbers(TreeNode* root) {
        // write code here
        if(!root)//特殊情况
            return 0;
        int sum = 0;
        return preorder(root, sum);
    }
    
    int preorder(TreeNode* root, int sum){
        if(root == NULL)
            return 0;
        sum = sum * 10 + root->val;//一层一层进行遍历
        if(!root->left && !root->right)//没有子结点
            return sum;
        return preorder(root->left, sum) + preorder(root->right, sum);
    }
};

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int sumNumbers(TreeNode* root) {
        // 通过在vector中保存路径来计算结果
        if(root == nullptr)
            return 0;
        vector temp;
        vector paths;
        path(temp, root, paths);
        //对paths里记录的内容进行求和
        int sum = 0; //最终结果
        for(auto &i : paths){
            int line = 0; //记录单个路径的和
            for(auto &j : i){
                line = line*10+j;
            }
            sum += line;
        }
        return sum;
    }
    
    void path(vector&temp, TreeNode* root, vector &paths){
        if(root == nullptr) 
            return;
        temp.push_back(root->val);
        if(root->left==nullptr && root->right==nullptr)
            paths.push_back(temp); //将根节点到叶子节点的一个路径记录到paths中
        if(root->left)
            path(temp, root->left, paths);
        if(root->right)
            path(temp, root->right, paths);
        temp.pop_back();
    }
};