NC 8 二叉树根节点到叶子节点和为指定值的路径
情景提要
牛客题解系列，按照题号顺序开始。
NC8
01
题目描述
返回
[[5,4,11,2],
[5,8,9]]
02
输入输出示例
输入:
{1,2} 1
输出:
[]
03
题目分析
思路
本题和NC5 几乎是一样的，依然是递归和迭代两种方法都可以做，只需要改变一下到了根节点时的判断条件就可以了。这里靓仔就偷个懒，只写一下递归的方法啦。
和NC5不一样的是，这里靓仔并没有修改树的结点值，而是使用了中间变量，用的回溯的思想。改变结点的值还是使用中间变量，只是程序实现的两种方式而已。
03
代码实现
方法
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/class Solution {public:/**** @param root TreeNode类* @param sum int整型* @return int整型vector<vector<>>*/// 回溯vector<vector<int> > res;vector<int> tmp;vector<vector<int> > pathSum(TreeNode* root, int sum) {// write code hereif(root){tmp.push_back(root->val);travel(root,sum,root->val);}return res;}void travel(TreeNode* root,int sum,int cursum){if(root->left){tmp.push_back(root->left->val);travel(root->left,sum,cursum+root->left->val);tmp.pop_back();}if(root->right){tmp.push_back(root->right->val);travel(root->right,sum,cursum+root->right->val);tmp.pop_back();}else if(!root->left && !root->right){if(sum == cursum) res.push_back(tmp);return;}}};
04
总结
又是一道之前题目的小变体哦。
欢迎评论区留言讨论哦