給定一個二叉樹和一個目標和，找到所有從根節點到葉子節點路徑總和等于給定目標和的路徑。

說明:?葉子節點是指沒有子節點的節點。

示例:
給定如下二叉樹，以及目標和?sum = 22，

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

返回:

[[5,4,11,2],[5,8,4,5] ] //我的錯誤代碼：（留著以后找思路錯誤處） /*** 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 {vector<vector<int>> ans;vector<int> temp; public:vector<vector<int>> pathSum(TreeNode* root, int sum) {if(root==NULL) return ans;helper(root,sum, root->val);return ans;}void helper(TreeNode* root, int sum, int s){if(root==NULL) return;sum -= root->val;temp.push_back(root->val);if(root->left == NULL && root->right == NULL){if(sum == 0){ans.push_back(temp);temp.clear();temp.push_back(s); }else if(sum < 0){temp.pop_back();return;}} if(root->left) helper(root->left,sum,s);if(root->right) helper(root->right,sum,s);return;} };

?

大佬正確代碼：

/*** 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<vector<int>> pathSum(TreeNode* root, int sum) {vector<int> v;vector<vector<int>> vv;DFS(vv,v,root,sum);return vv;}void DFS(vector<vector<int>> &vv,vector<int> v,TreeNode* root,int sum){if(!root)return;sum = sum-root->val;v.push_back(root->val);if(!sum && !root->left && !root->right)vv.push_back(v);DFS(vv,v,root->left,sum);DFS(vv,v,root->right,sum);} };

我的修改過的正確代碼：

?

/*** 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 {vector<vector<int>> ans;vector<int> temp; public:vector<vector<int>> pathSum(TreeNode* root, int sum) {if(root==NULL) return ans;helper(root,sum);return ans;}void helper(TreeNode* root, int sum){if(root==NULL) return;sum -= root->val;temp.push_back(root->val);if(root->left == NULL && root->right == NULL){if(sum == 0){ans.push_back(temp); }} if(root->left) helper(root->left,sum);if(root->right) helper(root->right,sum);temp.pop_back(); //回溯return;} };

總結：

此題是需要回溯的，回溯要放在遞歸之后 ！

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的leetcode--113.路径总和 Ⅱ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。