二叉树根节点到叶子节点的所有路径数字和

题目描述

给定一个仅包含数字 0−9 的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
例如根节点到叶子节点的一条路径是 1→2→3,那么这条路径就用 123 来代替。
找出根节点到叶子节点的所有路径表示的数字之和

解题思路

这道题要求所有路径的和，那么首先想到使用dfs遍历出所有的从根节点到叶子节点的路径，注意边界情况，每次使用一个临时数组存入已经到达的节点的val，当然每次遍历完一个节点的子节点之后要将当前值pop出来，将所有的路径经过的节点的val存入数组中，到达叶子节点后再插入res中，那么最终会得到一个二维数组res。

最后将res中每一行做一个十进制的累加运算，将这些运算结果相加即可。
代码如下，很简洁。

C++

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

class Solution {
public:

    vector<vector<int>> res;
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int sumNumbers(TreeNode* root) {
        if(root==nullptr) return 0;
        // 临时保存当前路径经过的节点的值
        vector<int> t;
        addSum(t,root);
        int sum = 0;
        // 对二维数组求和
        for(auto i: res){
            // 对每一行求和
            sum+=calSum(i);
        }
        return sum;
    }

    int calSum(vector<int> v){
        int res=0;
        for(int i=0;i<v.size();i++){
            res = res*10+v[i];
        }
        return res;
    }

    void addSum(vector<int> temp, TreeNode* root){
        if(root==nullptr) return;
        temp.push_back(root->val);
        if(root->left==nullptr&&root->right==nullptr){
            res.push_back(temp);
        }
        if(root->left) addSum(temp, root->left);
        if(root->right) addSum(temp, root->right);
        temp.pop_back();
    }
};