LeetCode 113 Path Sum II

Train of thought

By recursing to the leaf node and then adding up the nodes along the path. At each recursion, val of the current node is added to the last location of the path, and the recursion ends with the last location of the val popping up.

code

class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int sum) { if (! root) return {}; vector<int> path; vector<vector<int>> rs; DFS(root, sum, path, rs); return rs; } void DFS(TreeNode *root, int sum, vector<int> &path, vector<vector<int>> &rs) { if (! root) return ; path.push_back(root->val); DFS(root->left, sum, path, rs); DFS(root->right, sum, path, rs); if (! root->left && ! root->right) { for (const auto &num : path) sum -= num; if (! sum) rs.push_back(path); } path.pop_back(); }};Copy the code

conclusion

= = = = = = = = = = = = = = = = = = = root->left && ! Root ->right, then calculate the path and, since you want to start from root, directly through the entire path. In other cases, sometimes the last node of the path is not a leaf node, so no! root->left && ! Root – > right conditions. If the path does not necessarily start from root, you do not need to traverse the entire path and then judge. Path Sum III is displayed