112. Path Sum

自己的一个错误写法：

class Solution {public:    bool hasPathSum(TreeNode* root, int sum) {        if(root == NULL)            return false;        int value = 0;        return hasPathSum(root,sum,value);    }    bool hasPathSum(TreeNode* root,int sum,int value){        if(root == NULL){            if(value == sum)                return true;            else                return false;        }        bool left = hasPathSum(root->left,sum,value + root->val);        bool right = hasPathSum(root->right,sum,value + root->val);        return left || right;    }};Input:[1,2]1Output:trueExpected:false

只有左右节点都为NULL时才是叶子节点，所以这个代码在例子[1,2]，1的右节点时就判断错误了，这个右节点虽然sum满足条件，但他本身不是叶子节点

 

正确写法：

class Solution {public:    bool hasPathSum(TreeNode* root, int sum) {        if(root == NULL)            return false;        if(!root->left && !root->right && root->val == sum)            return true;        return hasPathSum(root->left,sum - root->val) || hasPathSum(root->right,sum - root->val);    }};

 

113. Path Sum II 

class Solution {public:    vector
     
      
       > pathSum(TreeNode* root, int sum) {        vector
       
        
         > result;        vector
         
           res;        pathSum(root,sum,result,res);        return result;    }    void pathSum(TreeNode* root,int sum,vector
          
           
            >& result,vector
            
             & res){ if(root == NULL) return; res.push_back(root->val); if(!root->left && !root->right && root->val == sum) result.push_back(res); pathSum(root->left,sum - root->val,result,res); pathSum(root->right,sum - root->val,result,res); res.pop_back(); }};
            
           
          
         
        
       
      
     

 

第二种写法：

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
     
      
       > pathSum(TreeNode* root, int sum) {        vector
       
        
         > result;        vector
         
           res;        pathSum(root,sum,res,result);        return result;    }    void pathSum(TreeNode* root,int sum,vector
          
            res,vector
           
            
             >& result){ if(root == NULL) return; if(!root->left && !root->right && root->val == sum){ res.push_back(root->val); result.push_back(res); } res.push_back(root->val); pathSum(root->left,sum - root->val,res,result); pathSum(root->right,sum - root->val,res,result); return; }};
            
           
          
         
        
       
      
     

 

 

437. Path Sum III

注意:i只能到size-1，如果到size，就是把所有的和都减掉，相当于没有任何节点相加

class Solution {public:    int pathSum(TreeNode* root, int sum) {        vector
     
       res;        int num = 0;        int curSum = 0;        pathSum(root,sum,curSum,res,num);        return num;    }    void pathSum(TreeNode* root,int sum,int curSum,vector
      
       & res,int& num){        if(root == NULL)            return;        curSum += root->val;        if(curSum == sum)            num++;        res.push_back(root->val);        int t = curSum;        for(int i = 0;i < res.size() - 1;i++){            t -= res[i];            if(t == sum)                num++;        }        pathSum(root->left,sum,curSum,res,num);        pathSum(root->right,sum,curSum,res,num);        res.pop_back();    }};