Leetcode-112: path sum

112. The sum of the paths
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 . A leaf node is a node that has no children .

This question and question 257. All paths of binary tree Very similar , The code is similar .

Depth first （O(N),O(N)）

If you use depth first in this problem, you can use the previous sequence recursion simulation , But what we need to deal with in recursion is the calculation of the path sum of each node to ensure that it does not affect the path and calculation of other nodes , Therefore, if recursion is used, those redundant leaf nodes will need to be handled in the backtracking process .

As in the above path and calculation , The path sum of the first leaf node is calculated as 1+2+4, If the requirements are not met at this time , You need to go back , So update the existing results to 1+2, Using recursion can solve this problem perfectly , As in the following code return You can achieve effective backtracking .

if(root->left == nullptr && root->right == nullptr){
    
            if(num == target)   falg = true;
            //  Otherwise continue to recurse 
            return;
        }

The specific problem-solving code is as follows ：

class Solution {
    
public:
    void findPath(TreeNode* root,int num,int target,bool &falg){
    
        //  The node update path and 
        num += root->val;
        //  To the leaf node 
        if(root->left == nullptr && root->right == nullptr){
    
            //  Satisfy the solution conditions , Result flag is true 
            if(num == target){
    
                falg = true;
            }   
            //  Otherwise continue to recurse 
            return;
        }
        //  Left subtree recursion 
        if(root->left)  findPath(root->left,num,target,falg);
        //  Right subtree recursion 
        if(root->right) findPath(root->right,num,target,falg);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
    
        //  The root node is empty , return false
        if(root == nullptr) return false;
        // falg Used to mark the solution result 
        bool falg = false;
        findPath(root,0,targetSum,falg);
        return falg;
    }
};

breadth-first （O(N),O(N)）

Using breadth first is to simulate a sequence traversal . However, compared with ordinary printing path and other solutions , At this time, we need to maintain the existing paths and queues of each node . As shown in the figure below . Our path and queue are one-to-one corresponding to the tree node queue , in other words , The value of the path and queue at the same location as the tree node queue is the path and to the tree node .

class Solution {
    
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
    
        //  The empty tree returns directly false
        if(root == nullptr) return false;
        //  Initialize the tree node queue of breadth traversal 
        queue<TreeNode*> que;
        queue<int> num;
        que.push(root);
        num.push(root->val);
        //  If the queue is not empty, the node has not finished processing 
        while(!que.empty()){
    
            //  Take out the tree node queue and the first element of the path and queue 
            TreeNode* node = que.front();
            int res=num.front();
            que.pop();
            num.pop();
            //  If you reach the leaf node and the path and meet the requirements, you will directly jump out of the traversal , return true
            if(node->left==nullptr && node->right==nullptr && res==targetSum)
                return true;
            if(node->left){
    
                que.push(node->left);
                //  Next level nodes join the team , And the corresponding node path and storage 
                num.push(node->left->val + res);
            }  
            if(node->right){
    
                que.push(node->right);
                //  Next level nodes join the team , And the corresponding node path and storage 
                num.push(node->right->val + res);
            }  
        }
        //  After the node is processed, the addition is still not found targetSum The path of , return false
        return false;
    }
};