Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Why DFS

I believe that the friends who have learned data structure know that DFS (depth-first search) is a very important search algorithm, may directly say that you feel not conditional you can go to see some algorithm competition. Every one of these games is going to involve DFS in some way or another, and DFS is probably something we all know about but we all know about it in order to avoid being too arrogant to write about it. In order to avoid this embarrassment we are going to take advantage of this activity for a few days to practice, well we don’t have to talk about fat.

PS: THESE days, I found that some fat friends do not know what DFS is. I’d better say it briefly, otherwise this problem will be difficult to do.

Depth First Search belongs to a graph algorithm, abbreviated as DFS, namely Depth First Search. The process is simply as deep as you can go into every possible branch path, and each node can only be accessed once.

For example, if we initiate A depth-first search from point A (the following access order is not unique, the second point could be either B or C or D), we might get an access process like A->B->E (no path! Backtrace to A)->C->F->H->G->D (no path, finally backtrace to A,A also has no adjacent node not visited, the search ends). The characteristic of depth-first search is briefly explained: the result of depth-first search must be a connected component of graph. Depth-first searches can be initiated from multiple points. If you sort each node by “end time” during a depth-first search (by creating a list, then adding that node to the end of the list if all of its neighbors have been accessed, and then reversing the entire list), Then we can get what is called “topological sort “, i.e. topological sort. [1]

The title

You are 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 where the values of all nodes add up to the target and targetSum. Return true if it exists; Otherwise, return false.

A leaf node is a node that has no children.

Example 1:

Enter: root = [5.4.8.11,null,13.4.7.2,null,null,null,1], targetSum = 22Output:trueExplanation: The path from the root node to the leaf node equal to the target sum is shown in the figure above.Copy the code

Example 2:

Enter: root = [1.2.3], targetSum = 5Output:falseThere are two root to leaf paths in the tree:1 --> 2) : and for3
(1 --> 3) : and for4There is no sum =5Path from the root node to the leaf node.Copy the code

The sample3: Enter: root = [], targetSum =0Output:falseExplanation: Since the tree is empty, there is no path from root to leaf.Copy the code

To recurse, you need to know where you end up. Then you need to choose who your variables are in your recursion and how they change. This sounds like backtracking. The idea is similar.

Solution: Top-down solution (slightly faster)

/** * 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 check(TreeNode root,int targetSum,int sum){
        if(root==null)return false;
        sum=sum+root.val;
        if(root.left==null&&root.right==null) {if(sum==targetSum)return true;
            else{
                return false; }}return check(root.left,targetSum,sum)||check(root.right,targetSum,sum);
    }
    public boolean hasPathSum(TreeNode root, int targetSum) {
        int sum=0;
        returncheck(root,targetSum,sum); }}Copy the code

Method 2:

If there is a path from the current node root to the leaf node, the sum of the paths is sum.

Given that the sum of the values from the root node to the current node is val, we can turn the big question into a smaller one: is there a path from the children of the current node to the leaf whose sum is sum-val?

If the current node is a leaf node, then we can directly determine whether sum is equal to val (since the path sum has already been determined, which is the value of the current node, we only need to determine whether the path sum satisfies the condition). If the current node is not a leaf node, we simply recursively ask its children if they meet the criteria.

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        returnhasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }}Copy the code

Solution 3: For the first time in history, we give you a full breadth first search to taste the new:

Thinking: First we can think of using breadth-first search to record the path sum from the root node to the current node to prevent double calculation.

So we use two queues that store the nodes to be traversed, and the paths and values from the root node to those nodes.

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();
        queNode.offer(root);
        queVal.offer(root.val);
        while(! queNode.isEmpty()) { TreeNode now = queNode.poll();int temp = queVal.poll();
            if (now.left == null && now.right == null) {
                if (temp == sum) {
                    return true;
                }
                continue;
            }
            if(now.left ! =null) {
                queNode.offer(now.left);
                queVal.offer(now.left.val + temp);
            }
            if(now.right ! =null) { queNode.offer(now.right); queVal.offer(now.right.val + temp); }}return false; }}Copy the code