Special topic of binary tree -- acwing 47 Path with a certain value in binary tree (preorder traversal)

The question ：

Enter a binary tree and an integer , Print out Sum of node values in a binary tree by Input integer Of All paths .

from Root node of tree Start Down to the leaf node Node passed Form a path .

Ensure the node value in the tree No less than 0.

Ideas ：

Traverse from top to bottom , When traversing the leaf node , Judge whether the current path weight sum is equal to the target value .

• if , Record the answer .

• If it is not , No operation

Code ：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
    
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {
    }
 * };
 */
class Solution {
    
public:
// take   Answer array  ans  As a global variable in the class , It is more convenient to record the answers .
    vector<vector<int>> res;
    vector<int> tmp;

    vector<vector<int>> findPath(TreeNode* root, int sum) {
    
        if(!root) return res;
        dfs(root, 0, sum);
        return res;
    }

    void dfs(TreeNode* rt, int sm, int sum)
    {
    
        if (sm > sum) return ;

        tmp.push_back(rt->val);// The former sequence traversal , Root left and right , Advanced vector 
        sm += rt->val;

        if (!rt->left && !rt->right)// leaf node 
        {
    
            if (sm == sum)
            {
    
                res.push_back(tmp);
            }
        }
		// The former sequence traversal , After traversing the root node above, the left 、 Right son 
        if (rt->left) dfs(rt->left, sm, sum);
        if (rt->right) dfs(rt->right, sm, sum);
        
		// Because you have to traverse other branches , Therefore, the scene must be restored 
        tmp.pop_back();
        sm -= rt->val;	// It doesn't matter ,sum What comes in is scalar , It's not the address 
    }
};