输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径
。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
(注意: 在返回值的list中,数组长度大的数组靠前)
class Solution { public: vector<vector<int> > res; //放外面即可 里面不能一直循环调用二维vector vector<int> temp;//保持一致 暂时用作缓存 int currentsum=0; int order=0; vector<vector<int> > FindPath(TreeNode* root,int expectNumber) { FindPath1(root, expectNumber); //if(root) dfsFind(root, expectNumber); return res; } public: void FindPath1(TreeNode* root,int expectNumber) //递归 调用 { if (root==nullptr)//传入空 return; currentsum+=root->val; temp.push_back(root->val); bool isleaf= (root->left==nullptr&&root->right==nullptr); if(isleaf&¤tsum==expectNumber) //是叶子节点 { res.push_back(temp); } if (root->left!=nullptr) //存在左子树 继续 FindPath1(root->left,expectNumber); if (root->right!=nullptr) //存在右子树 继续 FindPath1(root->right,expectNumber); //左中右 //每一段都会执行到此 currentsum-=root->val; temp.pop_back(); }
//牛客大神///////////////////////////////////////////////////////////////////////////////////////////////
void dfsFind(TreeNode * node , int left){
temp.push_back(node->val);
if(left-node->val == 0 && !node->left && !node->right)
res.push_back(temp);
else {
if(node->left) dfsFind(node->left, left-node->val);
if(node->right) dfsFind(node->right, left-node->val);
}
temp.pop_back();
}
原文:https://www.cnblogs.com/cgy1012/p/11391723.html