/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
回溯 和求某节点到根节点的路径差不多
只是这里找到符合条件的叶节点时,遍历继续走完就好
//======================================利用sum函数求和,看是否符合条件 class Solution { public: vector<vector<int>> ans; vector<int> temp; vector<vector<int>> pathSum(TreeNode* root, int target) { dfs(root, target); return ans; } void dfs(TreeNode* root, int target) { if (!root) return; temp.push_back(root->val); if (sum(temp) == target && !root->left && !root->right) {//和为target且为叶子结点时才对 ans.push_back(temp); } dfs(root->left, target); dfs(root->right, target); temp.pop_back(); } int sum(vector<int> a) { int s = 0; for (auto i : a) s += i; return s; } }; //-----------------------------------改进:push的时候sum+=,pop的时候sum-= class Solution { public: vector<vector<int>> ans; vector<int> temp; int sum = 0; vector<vector<int>> pathSum(TreeNode* root, int target) { dfs(root, target); return ans; } void dfs(TreeNode* root, int target) { if (!root) return; temp.push_back(root->val); sum += root->val;//这里改了但是效率提升不少 if (sum == target && !root->left && !root->right) {//和为target且为叶子结点时才对 ans.push_back(temp); } dfs(root->left, target); dfs(root->right, target); temp.pop_back(); sum -= root->val; } };