常熟有没有做阿里巴巴网站/网页设计和网站制作

路径总和

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

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

示例说明请见LeetCode官网。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：递归

首先，如果root为null，直接返回false。

否则，调用递归方法hasPathSum(TreeNode root, int targetSum, int curSum)，root为当前节点，targetSum为目标和，curSum当前路径上的累加和，递归过程如下：

• 如果root为null，直接返回；
• 否则，curSum累加当前节点的值；
• 然后判断如果root的左子树或者右子树有一边为null，则调用递归方法，参数为不为null的子树和curSum，然后返回；
• 如果root的左子树和右子树都不为null，则左右子树都要调用递归方法。

过程中当到达子节点时需要判断当前路径的和curSum和targetSum是否相等，如果相等，则将result更新为true，最后返回result。

说明：该题的解法过程和 LeetCode-111-二叉树的最小深度 完全一样。

public class LeetCode_112 {public static boolean result = false;public static boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) {return false;}hasPathSum(root, targetSum, 0);return result;}public static void hasPathSum(TreeNode root, int targetSum, int curSum) {if (root == null) {return;}curSum += root.val;if (root.left == null && root.right == null) {if (curSum == targetSum) {result = true;}return;}if (root.left == null && root.right != null) {hasPathSum(root.right, targetSum, curSum);return;}if (root.left != null && root.right == null) {hasPathSum(root.left, targetSum, curSum);return;}hasPathSum(root.left, targetSum, curSum);hasPathSum(root.right, targetSum, curSum);}public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);System.out.println(hasPathSum(root, 5));System.out.println(hasPathSum(root, 4));}
}

【每日寄语】 收集每一个快乐的瞬间，用它来回击每一个糟糕的日子。