一、题目
提示：
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
二、思路
回溯思想，dfs首先将当前的元素加入，然后判断到目前为止的temp数组是否满足sum=target的一种情况，如果不满足则继续递归遍历左子树和右子树。注意！！！当左子树和右子树都为空时，即当前节点为叶子结点了，到底的判断完了！！就把temp数组刚才存的最后一个（叶子）节点取出，下一步dfs递归刚才这个节点的【兄弟节点】！！
类似的回溯题目：
【LeetCode46】全排列（DFS）
【LeetCode39】组合总和（回溯法）
【LeetCode494】目标和（暴搜dfs或dp）
【LeetCode17】电话号码的字母组合（DFS回溯）
三、代码
/** * 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>>ans; vector<int>temp; int sum = 0; vector<vector<int>> pathSum(TreeNode* root, int target) { dfs(root, target); return ans; } void dfs(TreeNode* root, int target){ if(root == NULL){ return; } temp.push_back(root->val); sum += root->val; //到根节点了，并且sum满足条件 if(root->left == NULL && root->right == NULL && sum == target){ ans.push_back(temp); } dfs(root->left, target); dfs(root->right, target); //当左右孩子都为空的节点时，就把temp里最后的节点弹出，dfs弹出节点的兄弟节点 temp.pop_back(); sum -= root->val; } };
