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

1. Title Description

112. Sum of paths – LeetCode (leetcode-cn.com)

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:

Input: root = [13,4,7,2 5,4,8,11, null, null, null, null, 1], targetSum = 22 output: true interpretation: is equal to the target and the root node to leaf node path as shown in the above.Copy the code

Example 2:

Root = [1,2,3], targetSum = 5 output: false If sum is 4, there is no path from the root node to the leaf node where sum = 5.Copy the code

Example 3:

Input: root = [], targetSum = 0 Output: false Description: Since the tree is empty, there is no root to leaf path.Copy the code

Tip:

  • The number of nodes in the tree is in the range [0, 5000]
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

Second, train of thought analysis

  1. First check whether root is null. If not, perform depth-first search (DFS) :
  2. Introduce the parameter nowSum, which means the sum of the values that already exist before adding the values of the current node.
  3. DFS end condition: The left and right children are empty. If nowSum is equal to the expected value, return 1, otherwise return 0.
  4. If only one of the left and right children is empty, the search continues for the non-empty children and the sum of the current values is passed.
  5. If neither left nor right is empty, return 1 as long as one of the children returns 1.

AC code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; * /
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(! root)return false;
        return dfs(root,0,targetSum);
    }
    bool dfs(TreeNode* root,int nowSum,int targetSum)
    {
        nowSum+=root->val;
        if((! root->left)&&(! root->right)) {if(nowSum==targetSum)   return true;
            return false;
        }
        if(! root->left)return dfs(root->right,nowSum,targetSum);
        if(! root->right)return dfs(root->left,nowSum,targetSum);
        returndfs(root->right,nowSum,targetSum)||dfs(root->left,nowSum,targetSum); }};Copy the code

Model reference

Detailed popular thinking analysis, multiple solutions – Path summation – Force buckle (LeetCode) (leetcode-cn.com)