二叉树中和为某一值的路径
二叉树中和为某一值的路径
https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
我的方法比较直接，不是很巧妙但是能想得到，做的是加法。先序遍历的过程中把每个节点都存起来，一直到叶子节点算一条路径。
优点：这么做简单粗暴，容易想到。
缺点：容易出BUG，把心态搞崩。
废话不多说附上代码。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
//我用的是引用，没用全局变量。
void PerOrder(TreeNode* root,int number,vector<vector<int> > &res,int &sum){
if(root!=NULL){
if(res.empty()){
vector<int> tempres;
res.push_back(tempres);
}
sum += root->val;//先把节点值加上
res.back().push_back(root->val);
if(root->left!=NULL)
PerOrder(root->left,number,res,sum);
if(root->right!=NULL)
PerOrder(root->right,number,res,sum);
vector<int> tempres = res.back();
//判断此时sum不是number，或者不是叶子节点，把这条路径删掉。
if(sum!=number||root->left||root->right)
res.pop_back();
//为下一个节点做准备，还原sum值，和上一次路径节点。
sum -= root->val;
tempres.pop_back();
//不是根节点才能push
if(!tempres.empty())
res.push_back(tempres);
}
}
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<vector<int> > res;
int sum = 0 ;
PerOrder(root,expectNumber,res,sum);
//按照题目要求排序路径长的在前面
int n = res.size();
for(int i =0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(res[i].size()<res[j].size()){
vector<int> tempres;
tempres = res[i];
res[i] = res[j];
res[j] = tempres;
}
}
}
return res;
}
}; 
查看9道真题和解析