This is the sixth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Hello, everyone, today is the sixth day of my Participation in the August more text activity, today brings you about the binary tree related algorithm problem is to find the binary tree path sum, the text is as follows:

The title

You are given the root node of the binary tree and an integer targetSum representing the sum of the targets. Determine if there is a path from the root node to the leaf node in the tree where the values of all nodes add up to the target and the targetSum.

A leaf node is a node that has no children.

Example 1:

Example 2:

Example 3:

Enter: root = [1.2], targetSum = 0Output:false
Copy the code

Their thinking

Based on understanding the meaning of the question and the example given, we can use a depth-first search of DFS to find all paths from the root node to the leaf node, as long as a path whose sum equals the targetSum exists.

So, let’s implement this recursive logic:

1. Determine recursive function parameters and return types

Parameters: the root node of the binary tree, and a counter to calculate whether the sum of an edge of the binary tree is exactly equal to the target sum

Now the return value, when does a recursive function need to return a value? When do you not need a return value?

If you want to search for the entire binary tree, then the recursive function doesn’t have to return a value, and if you want to search for one of the paths that meets the criteria, then the recursive function has to return a value, because it has to return when it meets the criteria.

So, we can use the Boolean type.

2. Determine termination conditions

First of all, how does the counter count the sum of this path?

Instead of summing it up and trying to figure out if it’s equal to the target sum, which is a little bit cumbersome, you can decrement it, start the count with the target sum, and then each time you subtract the value of the node in the path that you’re traversing.

If count == 0 at the end, and the leaves are reached at the same time, then the target and the sum are found.

If I go through the leaves, and the count is not zero, it’s not found.

3. Determine the logic of single-layer recursion

Since the termination condition is to determine the leaf nodes, you should not recurse empty nodes.

Recursive functions have a return value. If a recursive function returns true, it has found a suitable path and should return immediately.

Code implementation

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        // If the remaining targetSum is equal to the value of the current node, if it is equal to the value of the current node, the path is through
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        } 
        
        returnhasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); }}Copy the code

The last

Complexity analysis

  • Time complexity: O(N), where N is the number of nodes in the tree. Each node is accessed once.

  • Space complexity: O(H), where H is the height of the tree. The spatial complexity is mainly determined by the overhead of stack space in recursion. In the worst case, the tree is chained and the spatial complexity is O(N). On average, the height of the tree is correlated logarithmically with the number of nodes, and the space complexity is order log N.