tags: LeetCode,backtracking https://leetcode.com/problems/path-sum-ii/
/** * 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) {} * }; */ class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int targetSum) { vector<vector<int>> r; if (root == nullptr) { return r; } if (root->left != nullptr) { auto left = pathSumSide(root-> left, root->val, targetSum); if (left.size() > 0) { left.insert(left.begin(), root->val); r.push_back(left); } } if (root->right != nullptr) { auto right = pathSumSide(root->right, root->val, targetSum); if (right.size() > 0) { right.insert(right.begin(), root->val); r.push_back(right); } } return r; } vector<int> pathSumSide(TreeNode* node, int sum, int targetSum) { vector<int> r; sum += node->val; if (node->left == nullptr && node->right == nullptr) { if (sum == targetSum) { r.push_back(node->val); return r; } } if (node->left != nullptr) { auto ret = pathSumSide(node->left, sum, targetSum); if (ret.size() > 0) { ret.insert(ret.begin(), node->val); return ret; } } if (node->right != nullptr) { auto ret = pathSumSide(node->right, sum, targetSum); if (ret.size() > 0) { ret.insert(ret.begin(), node->val); return ret; } } return r; } }; 失败的错误用例:
...