文章目录
一、题目描述二、思路三、代码
一、题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
二、思路
利用递归的思路，遍历二叉树的左右子树，判断从根节点走到叶子节点所经过的val和是否为给定的值。
三、代码
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if(root == nullptr)
return vv;
if(root != nullptr){
FindOnePath(root,expectNumber);
return vv;
}
}
void FindOnePath(TreeNode* root, int number){
temp.push_back(root->val); //把当前节点的值压入temp一维数组中
if(number == root->val && root->left == nullptr && root->right == nullptr){
vv.push_back(temp); //当遍历到叶子节点并且expectnumber的值等于一维数组的总和时，就把一维数组压入二维数组中
}
if(root->left != nullptr){
FindOnePath(root->left , number - root->val); //先遍历左子树
}
if(root->right != nullptr){
FindOnePath(root->right , number - root->val); //遍历右子树
}
temp.pop_back(); //如果遍历到叶子节点，但总和不为expectnumber时，就把当前节点移出数组
}
private:
vector<vector<int>> vv;
vector<int> temp;
};
