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

关键在于对叶子节点的判断。只有在叶子节点才会将路径和 push 进容器。

这个题算是和 NC8、NC9 一脉相承的

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

class Solution {
public:
    vector<vector<int>> NodeSums;
    void dfs(TreeNode*root, vector<int> partSum){
        if(!root) return;
        partSum.push_back(root->val);
        if(root->left == nullptr && root->right == nullptr){
            NodeSums.push_back(partSum);
        }
        dfs(root->left, partSum);
        dfs(root->right, partSum);
    }
    int sumNumbers(TreeNode* root) {
        dfs(root, {});
        // NodeSums 进行解析
        int allSum = 0;
        for(const auto & arr: NodeSums){
            int val = 0;
            for(int i =0; i < arr.size(); ++i){
                val += arr[i]*pow(10, arr.size() - i - 1);
            }
            allSum+=val;
        }
        return allSum;
    }
};