Leetcode 113. path sum II

Leetcode 113. The sum of the paths II

subject

Give you the root node of the binary tree root And an integer target and targetSum , Find out all From the root node to the leaf node The path sum is equal to the given target sum .

Leaf node A node without children .

Ideas

• First create a vector<vector> resuLt Result array , To save the path path Array
• The first sequence traversal , First, judge whether the left and right subtrees of the current node are empty ,count Is it 0, If it is , It shows that a path has been found , Store the path
• Recursively traverses the left subtree , First, save the current node path in , Counter count Subtract the current node value , Then recursively traverse , If the return is unsuccessful , Directly undo the last stored result .

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:
    vector<vector<int>> result;
    vector<int> path;

    void traversal(TreeNode* cur,int count)
    {
    
        //  Leaf node encountered   also count = 0  Save the path 
        if(!cur->left && !cur->right && count == 0)
        {
    
            result.push_back(path);
            return;
        }
        //  Leaf node encountered and , And did not find the right side , Go straight back to 
        if(!cur->left && !cur->right)
        {
    
            return;
        }
        if(cur->left)
        {
    
            //  Recursively traverses the left subtree 
            path.push_back(cur->left->val);//  Save the current node value 
            count -= cur->left->val;

            traversal(cur->left,count); //  recursive 

            count += cur->left->val;//  to flash back 
            path.pop_back();//  to flash back 

        }
        if(cur->right)
        {
    
            //  Recursively traverses the right subtree 
            path.push_back(cur->right->val);
            count -= cur->right->val;

            traversal(cur->right,count);//  recursive 

            count += cur->right->val;//  to flash back 
            path.pop_back();//  to flash back 
        }

        return;
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    
        result.clear();
        path.clear();
        if(root == NULL)
        {
    
            return result;
        }
        path.push_back(root->val);//  Send the root node into the path 
        traversal(root,targetSum - root->val);
        return result;
    }
};