题目

113 路径总和II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
image.png

思路

本题和leetcode257基本一样，257是求每条路径，本题只要找到路径上总和与target相等的路径即可，比257多了比较的操作。
遍历整个树，找到所有路径，所以递归函数不要返回值（返回值只能返回一个），要用返回参数！

解题代码如下，和257基本一样：

  1. class Solution
  2. {
  3. public:
  4.     vector<vector<int>> pathSum(TreeNode *root, int targetSum)
  5.     {
  6.         vector<int> path;
  7.         vector<vector<int>> result;
  8.         getPaths(root, targetSum, path, result);
  9.         return result;
  10.     }
  12. private:
  13.     void getPaths(TreeNode *node, int target, vector<int> &path, vector<vector<int>> &result)
  14.     {
  15.         if (node == nullptr)
  16.             return;
  18.         path.push_back(node->val);
  19.         //判断当前节点是否是叶子节点
  20.         if (node->left == nullptr && node->right == nullptr)
  21.         {
  22.             int sum = 0;
  23.             for (auto p : path)
  24.             {
  25.                 sum += p;
  26.             }
  27.             if (sum == target)//判断和是否相等
  28.                 result.push_back(path);
  29.             return;
  30.         }
  31.         //不是叶子节点，分别遍历其左子树和右子树
  32.         if (node->left != nullptr)
  33.         {
  34.             getPaths(node->left, target, path, result);
  35.             path.pop_back(); //回溯，移除node->left
  36.         }
  37.         if (node->right != nullptr)
  38.         {
  39.             getPaths(node->right, target, path, result);
  40.             path.pop_back(); //回溯，移除node->right
  41.         }
  42.         return;
  43.     }
  44. };

leetcode 112

112是本题的简化版，只需要返回bool类型。两种解法：

  1. 还是用本题的递归函数，主函数只需要判断result是否为空即可
  2. 因为我们需要的是bool，所以可以构造一个返回值为bool的递归函数：bool hasPathsSum(TreeNode *node, int target, vector<int> &path)