Path to the combined

Given the root node of the binary tree and an integer targetSum representing the targetSum, determine if there is a path from the root node to the leaf node in the tree. The sum of all the nodes in the path is equal to the target and targetSum.

Leaf nodes are nodes that have no children.

See the LeetCode website for an example.

Source: LeetCode Link: https://leetcode-cn.com/probl… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution 1: Recursion

First, if root is null, simply return false.

Otherwise, call the recursive method aspathsum (TreeNode root, int targetSum, int curSum), root is the current node, targetSum is the targetSum, curSum is the sum of the current path, recursive process is as follows:

  • If root is null, return directly;
  • Otherwise, curSum sums the value of the current node;
  • If one side of root’s left subtree or right subtree is null, call the recursive method with non-null subtree and curSum, and return;
  • If neither the left subtree nor the right subtree of root is NULL, then both the left and right subtrees call recursive methods.

When a child node is reached, it is necessary to determine whether the current path is equal to curSum and targetSum. If so, result will be updated to true, and result will be returned.

Leetcode -111- the minimum depth of the binary tree is exactly the same.

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)); }}

【 Daily Message 】
Collect every happy moment and use it to fight back against every bad day.