手撕力扣：路径总和

力扣112. 路径总和 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。 完整思路版：

class Solution { private: bool traversal(TreeNode* cur, int count) { if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0 if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回 if (cur->left) { // 左 count -= cur->left->val; // 递归，处理节点; if (traversal(cur->left, count)) return true; count += cur->left->val; // 回溯，撤销处理结果 } if (cur->right) { // 右 count -= cur->right->val; // 递归，处理节点; if (traversal(cur->right, count)) return true; count += cur->right->val; // 回溯，撤销处理结果 } return false; } public: bool hasPathSum(TreeNode* root, int sum) { if (root == NULL) return false; return traversal(root, sum - root->val); } };

精减版：

class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if (root == NULL) return false; if (!root->left && !root->right && sum == root->val) { return true; } return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); } };

力扣113. 路径总和II 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 思路：路径总和II要遍历整个树，找到所有路径，所以递归函数不要返回值。

class Solution { private: vector<vector<int>> result; vector<int> path; // 递归函数不需要返回值，因为我们要遍历整个树 void traversal(TreeNode* cur, int count) { if (!cur->left && !cur->right && count == 0) { // 遇到了叶子节点切找到了和为sum的路径 result.push_back(path); return; } if (!cur->left && !cur->right) return ; // 遇到叶子节点而没有找到合适的边，直接返回 if (cur->left) { // 左 （空节点不遍历） path.push_back(cur->left->val); count -= cur->left->val; traversal(cur->left, count); // 递归 count += cur->left->val; // 回溯 path.pop_back(); // 回溯 } if (cur->right) { // 右 （空节点不遍历） path.push_back(cur->right->val); count -= cur->right->val; traversal(cur->right, count); // 递归 count += cur->right->val; // 回溯 path.pop_back(); // 回溯 } return ; } public: vector<vector<int>> pathSum(TreeNode* root, int sum) { result.clear(); path.clear(); if (root == NULL) return result; path.push_back(root->val); // 把根节点放进路径 traversal(root, sum - root->val); return result; } }; 作者：carlsun-2 链接：https://leetcode-cn.com/problems/path-sum/solution/112-lu-jing-zong-he-di-gui-hui-su-die-dai-xiang-ji/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。