题解 | #二叉树中和为某一值的路径(二)#
二叉树中和为某一值的路径(二)
https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca
解答：简单dfs问题，遍历所有路径将满足条件的路径存入res即可。但有一点需要注意就是必须是叶子节点满足才行，如果非叶子节点和等于target也不能输出。时间复杂度因为遍历了所有节点所以为O(n),空间复杂度也为O(n)。
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> FindPath(TreeNode* root, int expectNumber) {
if (root == NULL)return res;
vector<int>tmp;
dfs(root, 0, expectNumber, tmp);
return res;
}
void dfs(TreeNode* root, int k, int tar, vector<int> tmp) {
if (root == NULL)return;
k += root->val;
tmp.push_back(root->val);
//必须为叶子节点才能输出
if (k == tar&&root->left==NULL&&root->right==NULL) {
res.push_back(tmp);
return;
}
dfs(root->left, k, tar, tmp);
dfs(root->right, k, tar, tmp);
}
};
途虎公司福利 103人发布