题目链接

LeetCode

题目描述

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

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

示例 1：

112. 路径总和 - 图1

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

示例 2：

112. 路径总和 - 图2

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

示例 3：

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

提示：

  • 树中节点的数目在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

    解题思路

    方法一：深度优先遍历

    观察要求我们完成的函数，我们可以归纳出它的功能：询问是否存在从当前节点 root 到叶子节点的路径，满足其路径和为 sum。

假定从根节点到当前节点的值之和为 val，我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val。

不难发现这满足递归的性质，若当前节点就是叶子节点，那么我们直接判断 sum 是否等于 val 即可（因为路径和已经确定，就是当前节点的值，我们只需要判断该路径和是否满足条件）。若当前节点不是叶子节点，我们只需要递归地询问它的子节点是否能满足条件即可。

  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.     bool hasPathSum(TreeNode* root, int targetSum) {
  15.         int sum = 0;
  16.         return dfs(root,targetSum);
  17.     }
  18.     bool dfs(TreeNode*root,int target){
  19.         if(root==nullptr)
  20.             return false;
  21.         target -= root->val;
  22.         if(root->left==nullptr&&root->right==nullptr){
  23.             if(0==target)
  24.                 return true;
  25.             return false;
  26.         }
  27.         bool res = dfs(root->left,target)||dfs(root->right,target);
  28.         target += root->val;
  29.         return res;
  31.     }
  32. private:
  33.     vector<int> path;
  34. };
  37. class Solution {
  38. public:
  39.     bool hasPathSum(TreeNode *root, int sum) {
  40.         if (root == nullptr) {
  41.             return false;
  42.         }
  43.         if (root->left == nullptr && root->right == nullptr) {
  44.             return sum == root->val;
  45.         }
  46.         return hasPathSum(root->left, sum - root->val) ||
  47.                hasPathSum(root->right, sum - root->val);
  48.     }
  49. };
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     boolean res = false;
  18.     public boolean hasPathSum(TreeNode root, int targetSum) {
  19.         dfs(root,targetSum);
  20.         return res;
  21.     }
  22.     private void dfs(TreeNode root, int targetSum){
  23.         if(res || root == null){
  24.             return;
  25.         }
  26.         targetSum -= root.val;
  27.         if(root.left == null&&root.right == null){
  28.             if(targetSum == 0){
  29.                 res = true;
  30.             }
  31.             return;
  32.         }
  33.         if(root.left != null){
  34.             dfs(root.left,targetSum);
  35.         }
  36.         if(root.right != null){
  37.             dfs(root.right,targetSum);
  38.         }
  39.     }
  40. }
  • 时间复杂度 O(N) ： N 为二叉树的节点数，需要遍历所有节点。
  • 空间复杂度 O(H) ： H为树的高度，递归栈的开销