LeetCode: Path Sum II

多数次过

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     void dfs(TreeNode *root, int sum, vector<vector<int>> &ret, vector<int> &tmp) {
13         if (!root) return;
14         tmp.push_back(root->val);
15         if (sum == root->val && !root->left && !root->right) ret.push_back(tmp);
16         if (root->left) dfs(root->left, sum-root->val, ret, tmp);
17         if (root->right) dfs(root->right, sum-root->val, ret, tmp);
18         tmp.pop_back();
19     }
20     vector<vector<int> > pathSum(TreeNode *root, int sum) {
21         // Start typing your C/C++ solution below
22         // DO NOT write int main() function
23         vector<vector<int>> ret;
24         vector<int> tmp;
25         dfs(root, sum, ret, tmp);
26         return ret;
27     }
28 };

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left;
 6  *     public TreeNode right;
 7  *     public TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<List<int>> PathSum(TreeNode root, int sum) {
12         List<List<int>> ans = new List<List<int>>();
13         List<int> tmp = new List<int>();
14         dfs(root, sum, ref ans, ref tmp);
15         return ans;
16     }
17     public void dfs(TreeNode root, int sum, ref List<List<int>> ans, ref List<int> tmp) {
18         if (root == null) return;
19         tmp.Add(root.val);
20         if (sum == root.val && root.left == null && root.right == null) ans.Add(new List<int>(tmp.ToArray()));
21         if (root.left != null) dfs(root.left, sum - root.val, ref ans, ref tmp);
22         if (root.right != null) dfs(root.right, sum -  root.val, ref ans, ref tmp);
23         tmp.RemoveAt(tmp.Count-1);
24     }
25 }

View Code