112. The sum of the paths

The difficulty is simple 800
Give you the root node of the binary tree root And an integer representing the sum of goals targetSum . Determine if there is Root node to leaf node The path of , The sum of the values of all nodes in this path is equal to the target and targetSum . If there is , return true ; otherwise , return false .
Leaf node A node without children .

 Example  1：

 Input ：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output ：true explain ： The root node to leaf node path equal to the target sum is shown in the figure above .
 Example  2：

 Input ：root = [1,2,3], targetSum = 5 Output ：false explain ： There are two paths from root node to leaf node in the tree ：
(1 --> 2):  And for  3
(1 --> 3):  And for  4
 non-existent  sum = 5  The path from the root node to the leaf node .
 Example  3：
 Input ：root = [], targetSum = 0 Output ：false explain ： Because the tree is empty , Therefore, there is no path from root node to leaf node .

Tips ：

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

Ideas

• Set the cumulative array , Traverse the journey down , Continue to accumulate
• Failure point ： The left and right nodes are handled separately , When dealing with the right node , Its value is equivalent to adding the root and left nodes respectively （ Setup queue , The left and right nodes enter together ）

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) {
    
        queue<TreeNode*> cur;// Nodes currently in the queue 
        queue<int> dp;
        int flag=0;// Can't find target Satisfied path 

        if(root==NULL) return 0;
        
        cur.push(root);
        dp.push(root->val);

        while(!cur.empty())
        {
    
            root=cur.front();
            cur.pop();
            int p=dp.front();
            dp.pop();
            if(p==targetSum){
    
                // Determine whether the leaf node 
                if(root->left==NULL&&root->right==NULL){
    
                    return 1;
                }
            }    
            // Zuo Zishu joins the team 
            if(root->left!=NULL){
    
                cur.push(root->left);
                int a=p+root->left->val;
                dp.push(a);
            }
            // Right subtree joins the team 
            if(root->right!=NULL){
    
            cur.push(root->right);
            int b=p+root->right->val;
                dp.push(b);
            }
        }
        return flag;

    }
};