本文共 2216 字，大约阅读时间需要 7 分钟。

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

5             / \            4   8           /   / \          11  13  4         /  \    / \        7    2  5   1

返回:

[   [5,4,11,2],   [5,8,4,5]]

思路很简单，就是往下搜索，但是写起来比较难。。。

这里贴一下我第一次瞎写的代码：

C++：

/** * 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
     
      
       > ve;           vector
       
         v1;           if(root==NULL)               return ve;           dfs(0,sum,root,ve,v1);           return ve;    }    void dfs (int sum,int target,TreeNode* root,vector
        
         
          >& ve,vector
          
           & v1) { if(root==NULL) return; if(root->left==NULL&&root->right==NULL) { if(sum+root->val==target) { v1.push_back(root->val); ve.push_back(v1); v1.pop_back(); } return ; } v1.push_back(root->val); dfs (sum+root->val,target,root->left,ve,v1); dfs (sum+root->val,target,root->right,ve,v1); v1.pop_back(); }};
          
         
        
       
      
     
    
   

 然后笨笨的我看了别人的代码，自己按照思路写了一遍， 成功超过了100% 的样例。 。。

改进后的代码：

C++：

/** * 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
     
      
       > ve;        vector
       
         v1;           if(root==NULL)               return ve;           v1.push_back(root->val);           dfs (root,sum,root->val,ve,v1);        return ve;    }    void dfs (TreeNode* root,int target,int sum,vector
        
         
          >& ve,vector
          
           & v1) { vector
           
            v2=v1; if(root->left==NULL&&root->right==NULL&&sum==target) { ve.push_back(v2); return; } if(root->left) { v1.push_back(root->left->val); dfs (root->left,target,sum+root->left->val,ve,v1); } if(root->right) { v2.push_back(root->right->val); dfs (root->right,target,sum+root->right->val,ve,v2); } } };
           
          
         
        
       
      
     
    
   

转载地址：http://tvaen.baihongyu.com/