-在二元树中找出和为某一值的所有路径--捡捡递归的使用
程序员文章站
2022-07-05 09:09:17
...
/* 算法要求:打印从root到叶节点的路径上的权值和 为指定数值的 所有路径 算法: 1、使用vector 类型的path来存放路径,避免回溯,递归函数之间的消息传递问题 2、注意遍历完左子树还要遍历右子树,所以在pos 1处不能有return 3、在递归的最后需要消除当前节点造成的影响,比如对path中pop_back当前的node。另外如果修改了curSum,则需要修正回去。 */ void printMatchPath(binTreeNode * node,int request,int curSum,vector<binTreeNode*> path) { if(node == NULL) return; if(node->left == NULL && node->right == NULL) { if(request == (node->data + curSum)) { for(int i=0;i<path.size();i++) { printf("%d ",((binTreeNode*)path[i])->data); } printf("%d\n",node->data); } return; } path.push_back(node);// pos 0 if(node->left != NULL) { //path.push_back(node);//pos 1:这个会和pos 2处的代码重复执行,而且执行完之后没有消除影响。 printMatchPath(node->left,request,curSum + node->data,path); } if(node->right != NULL) { //path.push_back(node);//pos 2:处的代码重复执行,就会把当前节点入栈两次,所以需要把这些共有的操作 提到前边 printMatchPath(node->right,request,curSum + node->data,path); } //需要清楚当前节点造成的对curSum的影响,但是此处没有修改curSum所以就不需要额外的操作了 path.pop_back();//消除 对path造成的影响 }
最近的代码能力严重下降,
捡捡 递归的使用
上一篇: java取消科学计数法
下一篇: Random()随机数+随机切换图片