首页 > 代码库 > Cracking the Coding Interview 4.8
Cracking the Coding Interview 4.8
You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree-it does not have to start at the root.
思路：
既然路径的开始不一定在根，那么找出从根开始的所有路径就不够了。每个节点都有可能是开始，也有可能是结束。将任一节点当做结束节点，倒推至根节点，路径上只要有和为value，就是一个满足的路径，但是找到一个还不能停，一直要倒推到根为止，因为可能倒推序列是2+3-1+1，如果value是5，那么2+3满足，但2+3-1+1也满足，因此我们一直要倒推到根，才能找出所有的路径。
void func(Node *n,int *buf,int level,int sum)//n是结束节点，buf里存放了从该节点到根每个节点上的key，level是深度，sum是要求的和{ if(n == NULL) { return; } buf[level]=n->key; int temp = sum; for(int i=level;i>=0;i--) { temp-=buf[i]; if(temp==0) { for(int j=i;j<level;j++) { printf("%d,",buf[j]); } printf("%d\n",buf[level]); } } func(n->left,buf,level+1,sum); func(n->right,buf,level+1,sum);}
Cracking the Coding Interview 4.8
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。