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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    
    int res = 0;
    int sumNumbers(TreeNode* root) {
        // write code here
       if(root == NULL){
           return 0;
       } 
       
       vector<int> path;
       sumNumbersWithPath(root, path);
//        printf("res = %d\n",res);
       return res;
    }
    
    void sumNumbersWithPath(TreeNode* root,vector<int> &path) {
        // write code here
       if(root == NULL){
           return;
       } 
       
       path.push_back(root->val);
       if(root->left == NULL && root->right == NULL){
           int val = 0;
           for(int i=0;i<path.size();i++){
               val *= 10;
               val += path[i];
//                printf("path[%d] = %d",i,path[i]);
           }
//            printf("\n");
//            printf("val = %d\n",val);
           res += val;
           return;
       }
        
       if(root->left != NULL){
           sumNumbersWithPath(root->left,path);
           path.pop_back();
       }
        
        if(root->right != NULL){
           sumNumbersWithPath(root->right,path);
           path.pop_back();
       }
       return;
    }
};


简化版本：
这个妙在如果root为空返回0，不参加计算这个上面。
细细品味。。

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    
    int sumNumbers(TreeNode* root) {
        // write code here
       return dfs(root,0);
    }
    
    int dfs(TreeNode* root,int val) {
        // write code here
       if(root == NULL){
           return 0;
       } 
       
       val = root->val + val * 10;
       if(root->left == NULL && root->right == NULL){
           return val;
       }

       return dfs(root->left,val) + dfs(root->right,val);
    }
};