AcWing 47. 二叉树中和为某一值的路径
原题链接
中等
作者:
Tom_
,
2023-10-06 20:30:02
,
所有人可见
,
阅读 62
要求
- 需要是一条路径(从根节点开始,直到叶子结点),可以使用先序遍历
- 不可以是子路径,也就是说,如果在中途
sum = target
并且和剩下子节点构成的路径中,子孙节点不全为0(假如这个节点的子孙节点全为0,那么与子孙节点 一起构成的所有路径均为目标路径),那么这个路径不能作为结果
代码
/**
* 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 {
private:
vector<vector<int>> patharr = {};
// 题目可以使用先序遍历(或其他遍历)方法来解决
// 不要试图用引用来传递pathway,那样会导致递归后无法恢复递归前状态,导致出错!
void path(TreeNode* root, vector<int> pathway, int sum, int target) {
if(root == nullptr) return;
pathway.push_back(root->val);
sum += root->val;
// 如果当前的值等于目标值
if(target == sum) {
// 要保证是一条路径(即本节点没有子节点)
if(!root->left && !root->right) {
// 若是一条路径且当前值等于目标值,就将当前的路径加入到路径集合中
patharr.push_back(pathway);
// 注意,如果是一条路径则返回
// 如果当前值等于目标值但是还有子节点,那么就不应该返回,因为这个时候子节点可能全为0
// AC的测试用例似乎没有考虑这种情况。
return;
}
}
path(root->left, pathway, sum, target);
path(root->right, pathway, sum, target);
}
public:
vector<vector<int>> findPath(TreeNode* root, int sum) {
path(root, {}, 0, sum);
return patharr;
}
};