【leetcode】Path Sum II

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 <iostream>2 #include <vector>3 #include <stack>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<vector<int> > answer;
17 public:
18     vector<vector<int> > 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<int> 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<vector<int> > a = s.pathSum(treenode,9);
53     for(int i = 0;i < a.size();i++){
54         std::vector<int> v = a[i];
55         for(int j = 0;j < v.size();j++)
56             cout << v[j]<<" ";
57         cout <<endl;
58     }
59 
60 }

?