Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:

Given the below binary tree and sum = 22,

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

return

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

---

下午做了个笔试没睡觉，晚上整个人都不好了，一点刷题的感觉都没有。 很容易想到用深度有限搜索。开始想用栈实现，结果写的乱七八槽，后来才改成用递归实现深搜。 用数组path记录从根节点到当前的路径，如果当前节点是叶节点并且找到合适的路径，就把path转成vector放入结果的二维vector中；如果当前不是叶节点，就假定它在路径上，把它放入path中，并且把sum减掉当前节点的val，供递归时候使用。 代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 struct TreeNode { 7     int val; 8     TreeNode *left; 9     TreeNode *right;10     TreeNode(int x) : val(x), left(NULL), right(NULL) {}11 };12  13 class Solution {14 private:15     int path[10000];16     vector
        
         
           > answer;17 public:18     vector
          
           
             > pathSum(TreeNode *root, int sum) {19 dfs(root,sum,0);20 return answer;21 }22 void dfs(TreeNode* root,int sum,int path_index){23 if(root == NULL)24 return;25 if(root->val == sum && root->left == NULL && root->right == NULL)26 {27 //找到一条路径28 vector
            
              temp;29 for(int i= 0;i < path_index;i++)30 temp.push_back(path[i]);31 temp.push_back(sum);//叶节点这里才进入向量32 answer.push_back(temp);33 }34 else{35 sum -= root->val;36 path[path_index++] = root->val;37 if(root->left != NULL)38 dfs(root->left,sum,path_index);39 if(root->right != NULL)40 dfs(root->right,sum,path_index);41 }42 }43 };44 int main(){45 TreeNode* treenode = new TreeNode(5);46 TreeNode* left = new TreeNode(4);47 treenode->left = left;48 TreeNode* right = new TreeNode(8);49 treenode->right = right;50 51 Solution s;52 vector
             
              
                > a = s.pathSum(treenode,9);53 for(int i = 0;i < a.size();i++){54 std::vector
               
                 v = a[i];55 for(int j = 0;j < v.size();j++)56 cout << v[j]<<" ";57 cout <