leetcode：113. 路径总和 II

题目

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

示例 1：
[中等] 113. 路径总和 II - 图1

  1. 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
  2. 输出：[[5,4,11,2],[5,8,4,5]]

示例 2：
[中等] 113. 路径总和 II - 图2

  1. 输入：root = [1,2,3], targetSum = 5
  2. 输出：[]

示例 3：

  1. 输入：root = [1,2], targetSum = 0
  2. 输出：[]

解答 & 代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     vector<vector<int>> resultPaths;    // 结果，即所有满足条件的路径
  15.     vector<int> curPath;                // 当前路径（所有节点的值）
  16.     // 递归，深度优先遍历
  17.     void dfs(TreeNode* root, int targetSum)
  18.     {
  19.         if(root == nullptr)
  20.             return;
  22.         // 前序位置：
  23.         curPath.push_back(root->val);    // 在路径中加入当前节点的值
  24.         targetSum -= root->val;            // 将剩余目标减去当前节点的值
  25.         // 如果当前是叶子节点
  26.         if(root->left == nullptr && root->right == nullptr)
  27.         {
  28.             // 如果当前剩余目标为 0，说明找到一条满足条件的路径，存入结果数组
  29.             if(targetSum == 0)        
  30.                 resultPaths.push_back(curPath);            
  31.         }
  32.         else
  33.         {
  34.             // 递归处理左子树、右子树
  35.             dfs(root->left, targetSum);
  36.             dfs(root->right, targetSum);
  37.         }
  38.         // 后序位置：即将离开当前节点，撤销当前节点的影响
  39.         curPath.pop_back();                // 将当前节点从路径中弹出
  40.         targetSum += root->val;            // 将剩余目标值重新加回当前节点的值
  41.     }
  42. public:
  43.     vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
  44.         dfs(root, targetSum);
  45.         return resultPaths;
  46.     }
  47. };

复杂度分析：设二叉树共 N 个节点

  • 时间复杂度 O(N)：遍历每个节点一次
  • 空间复杂度 O(log N)：
    • 栈空间取决于递归深度，即二叉树的高度，空间复杂度 O(log N)
    • curPath 数组存储当前的路径，空间复杂度也是数的高度 O(log N)
    • 结果数组 resultPaths 的复杂度不计

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 93.01% 的用户
  4. 内存消耗：19.2 MB, 在所有 C++ 提交中击败了 91.00% 的用户