Leetcode 112. path sum

Leetcode 112. The sum of the paths

subject

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 .

Ideas

• Use the method of preorder traversal
• Determine the parameters and return values of recursive functions ： The root node of the binary tree and a counter , The counter is used to calculate whether the node on a path of the binary tree is equal to the target value
• Determine termination conditions ： Initialize the counter to the target value , Traverse one node at a time , Just subtract the node value , If the current node is a leaf node and count = 0, It shows that such a path has been found . If the leaf node is found, but count != 0, It indicates that this path does not conform to , Prepare to go back .
• Single layer recursive logic ： Recursively traverses the left subtree , Recursively traverses the right subtree , First count Subtract the value of the node , If it doesn't , Directly rollback the node value .

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 traversakl(TreeNode* cur,int count)
    {
    
        //  A leaf node is encountered and count = 0
        if(!cur->left && !cur->right && count == 0)
        {
    
            return true;//  Recursive export 
        }

        if(!cur->left && !cur->right)
        {
    
            //  Leaf node encountered   also count != 0  It indicates that this path does not conform to 
            return false;//  Recursive export 
        }

        if(cur->left != NULL)
        {
    
            count -= cur->left->val;//  Recursive left subtree 
            if(traversakl(cur->left,count))
            {
    
                return true;
            }
            count += cur->left->val;//  to flash back   Cancel processing result 
        }

        if(cur->right != NULL)
        {
    
            count -= cur->right->val;
            if(traversakl(cur->right,count))
            {
    
                return true;
            }
            count += cur->right->val;
        }

        return false;
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
    
        if(root == NULL)
        {
    
            return false;
        }

        return traversakl(root,targetSum - root->val);
    }
};