leetcode：112. 路径总和

题目

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：
[简单] 112. 路径总和 - 图1

  1. 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
  2. 输出：true
  3. 解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：
[简单] 112. 路径总和 - 图2

  1. 输入：root = [1,2,3], targetSum = 5
  2. 输出：false
  3. 解释：树中存在两条根节点到叶子节点的路径：
  4. (1 --> 2): 和为 3
  5. (1 --> 3): 和为 4
  6. 不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

  1. 输入：root = [], targetSum = 0
  2. 输出：false
  3. 解释：由于树是空的，所以不存在根节点到叶子节点的路径。

解答 & 代码

解法一：分解的思路

分解的思路就类似于动态规划，需要明确递归函数的定义，用子问题的结果推导出大问题的结果。

  • 这里递归函数的定义：输入一个根节点 root，返回从根节点到叶子节点是否存在和为 targetSum 的路径
  • 大问题（root 这棵树是否存在和为 targetSum 的路径）可以分解为：只要左子树 or 右子树存在一条和为 targetSum - root->val 的路径，大问题就为 true，否则为 false

  • bad case：如果当前是叶子节点，结果取决于 root->val 是否等于 targetSum

    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. public:
    14.   // 递归函数的定义：输入一个根节点 root，返回从根节点到叶子节点是否存在和为 targetSum 的路径
    15.   bool hasPathSum(TreeNode* root, int targetSum) {
    16.       // 递归结束条件 1：遍历到 nullptr，直接返回 false
    17.       if(root == nullptr)
    18.           return false;
    19.       // 递归结束条件 2：如果当前是叶子节点，
    20.       // 若当前节点的值 == targetSum，则返回 true，否则返回 false
    21.       if(root->left == nullptr && root->right == nullptr)
    22.           return targetSum == root->val;
    24.       // 分解为子问题：如果左子树 or 右子树中存在一条满足条件的路径，就为 true，否则返回 false
    25.       return hasPathSum(root->left, targetSum - root->val) ||
    26.               hasPathSum(root->right, targetSum - root->val);
    27.   }
    28. };

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

  • 时间复杂度 O(N)：遍历每个节点一次

  • 空间复杂度 O(log N)：栈空间取决于递归深度，即二叉树的高度

执行结果：

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

解法二：遍历的思路

遍历的思路就类似于回溯算法，就是单纯的遍历回溯二叉树。