LeetCode - 路径和

问题陈述

鉴于 根 二叉树和整数 目标总和 ， 返回 真的 如果树有一个 从根到叶 路径，使得沿路径的所有值相加等于 目标总和 .

一个 叶子 是一个没有子节点的节点。

问题陈述取自： https://leetcode.com/problems/path-sum

示例 1：

Source: LeetCode

 输入：root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22  
 输出：真  
 说明：显示了具有目标总和的从根到叶的路径。

示例 2：

 输入：root = [1, 2, 3], targetSum = 5  
 输出：假  
 解释：树中有两条从根到叶的路径：  
 (1 --> 2)：总和为 3。  
 (1 --> 3)：总和为 4。  
 没有总和 = 5 的从根到叶的路径。

示例 3：

 输入：root = [], targetSum = 0  
 输出：假  
 解释：由于树是空的，所以没有从根到叶的路径。

约束：

 - 树中的节点数在 [0, 5000] 范围内。  
 - -1000 <= 节点.val <= 1000  
 - -1000 <= 目标总和 <= 1000

解释

递归

为了解决大多数与树相关的问题，最好的方法是使用递归方法或使用队列/堆栈。

这是我们将使用递归解决的简单问题之一。我们按照给定的步骤来解决问题：

• 递归移动到左右子树。在每次递归调用中，将总和减去当前节点的值。
• 在任何递归调用中，如果当前节点值等于剩余总和，则返回 true。这意味着存在具有给定目标的路径。

让我们先检查一下算法。

 - 如果根 == 空  
 - 返回假  
  
 - 如果 root->val == targetSum && root->left == null && root->right == null  
 - 返回真  
  
 -剩余目标=目标总和-根-> val  
  
 - 返回 hasPathSum(root->left, remainingTarget) || hasPathSum(root->right, remainingTarget)

让我们检查一下我们的算法 C++ , 戈朗 ， 和 Javascript .

C++ 解决方案

 类解决方案{  
 上市：  
 bool hasPathSum(TreeNode* root, int targetSum) {  
 如果（根 == NULL）{  
 返回假；  
 }  
  
 if(root->val == targetSum && root->left == NULL && root->right == NULL) {  
 返回真；  
 }  
  
 int remainingTarget = targetSum - root->val;  
  
 return hasPathSum(root->left, remainingTarget) || hasPathSum(root->right, remainingTarget);  
 }  
 };

Golang 解决方案

 func hasPathSum ( root * TreeNode , targetSum int ) bool { { .  
 如果根 == 无 {  
 返回假  
 }  
  
 如果 root.Val == targetSum && root.Left == nil && root.Right == nil {  
 返回真  
 }  
  
 剩余目标总和：=目标总和 - root.Val  
  
 返回 hasPathSum(root.Left, remainingTargetSum) || hasPathSum(root.Right, remainingTargetSum)  
 }

Javascript 解决方案

 var hasPathSum = function ( root , targetSum ) { ;  
 如果（根==空）{  
 返回假；  
 }  
  
 if(root.val == targetSum && root.left == null && root.right == null) {  
 返回真；  
 }  
  
 让剩余目标 = targetSum - root.val;  
  
 返回 hasPathSum(root.left, remainingTarget) || hasPathSum(root.right, remainingTarget);  
 };

让我们空运行我们的算法 示例 1 .

 输入：root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]  
 目标总和 = 22  
  
 第 1 步：如果 root == null  
 根在 5  
 错误的  
  
 第 2 步：如果 root->val == targetSum && root->left == NULL && root->right == NULL  
 5 == 22  
 错误的  
  
 第 3 步：剩余目标 = targetSum - root->val  
 = 22 - 5  
 = 17  
  
 第四步：返回 hasPathSum(root->left, remainingTarget) ||  
 hasPathSum(root->right, remainingTarget)  
  
 根->左= 4  
 根-> 右 = 8  
 剩余目标 = 17  
  
 第 5 步：如果 root == null  
 根在 4  
 错误的  
  
 第 6 步：如果 root->val == targetSum && root->left == NULL && root->right == NULL  
 4 == 17  
 错误的  
  
 第 7 步：remainingTarget = targetSum - root->val  
 = 17 - 4  
 = 13  
  
 第 8 步：返回 hasPathSum(root->left, remainingTarget) ||  
 hasPathSum(root->right, remainingTarget)  
  
 根->左= 11  
 根-> 对 = 无  
 剩余目标 = 13  
  
 第 9 步：如果 root == null  
 根在 11  
 错误的  
  
 第 10 步：如果 root->val == targetSum && root->left == NULL && root->right == NULL  
 11 == 13  
 错误的  
  
 第 11 步：剩余目标 = targetSum - root->val  
 = 13 - 11  
 = 2  
  
 第 12 步：返回 hasPathSum(root->left, remainingTarget) ||  
 hasPathSum(root->right, remainingTarget)  
  
 根->左= 7  
 根-> 右 = 2  
 剩余目标 = 2  
  
 第 13 步：如果 root == null  
 根在 7  
 错误的  
  
 第 14 步：如果 root->val == targetSum && root->left == NULL && root->right == NULL  
 7 == 2  
 错误的  
  
 第 15 步：remainingTarget = targetSum - root->val  
 = 2 - 7  
 = -5  
  
 第16步：返回hasPathSum(root->left, remainingTarget) ||  
 hasPathSum(root->right, remainingTarget)  
  
 根->左=空  
 根->右=空  
 剩余目标 = -5  
  
 第 17 步：如果 root == null  
 根为空  
 真的  
  
 我们回到第 16 步  
  
 第 18 步：如果 root == null  
 根为空  
 真的  
  
 我们回到第 12 步  
  
 第 19 步：如果 root == null  
 根在 2  
 错误的  
  
 第 20 步：如果 root->val == targetSum && root->left == NULL && root->right == NULL  
 2 == 2  
 真的  
  
 我们在这里返回 true 并回溯到树的其余部分。  
 最后，我们有OR条件并且找到了一次路径  
 我们将答案返回为真。

最初发表于 https://alkeshghorpade.me .

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明

本文链接：https://www.qanswer.top/12190/47230411