`
Before_Morning
  • 浏览: 34968 次
文章分类
社区版块
存档分类
最新评论

(四)在二元树中找出和为某一值的所有路径

 
阅读更多

百度面试题目:

输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数 22 ,如下图二元树:
10
/ \
5 12
/ \
4 7

则打印出两条路径:10, 1210, 5, 7

分析:看到该题目的第一反应是:递归+回溯。首先当然要保存搜索的路径,并记录当前路径上所有元素的和。如果累积和与当前节点值的和大于输入的整数data,则将不进行加法运算,直接回退;如果与当前节点值的和刚好等于sum,且当前节点为叶子节点,则打印该路径,然后回退;如果与当前节点值得和小于data,则继续向下计算……,这样的做法似乎很合理,其实呢?很显然,如果这样做,我们就为问题添加了一个条件:即二元树上的元素值均为正数!!!题目显然没有给出这个条件。自然算法就错了……

正确的做法应该是这样的:首先当然仍要保存搜索的路径,并记录当前路径上所有元素的和sum。如果当前节点为叶子节点,并且当前节点值与sum的和等于data,则满足条件,打印后递归返回到父节点,注意在打印后、递归返回之前要先减去当前节点元素的值;如果当前节点不是叶子节点,则不必判断当前节点值与sum的和是否等于data,继续访问子节点……

另一种类似的方法不用录当前路径上所有元素的和sum,而是使用期望的和依次减去访问到的节点的值……最后是判断到达叶子节点时期望和是否减为0,其实时类似的……看代码实现:

#include<stdio.h>
#include<stdlib.h>
#define MAX 20

struct BiTreeNode
{
int data;
struct BiTreeNode *left;
struct BiTreeNode *right;
};

/*递归创建二叉排序树,以'-1'结束*/
BiTreeNode * CreateBSTree()
{
int data;
BiTreeNode * tr;
scanf("%d",&data);
if(data==-1)
{
return NULL;
}
else
{
tr = (BiTreeNode *)malloc(sizeof(BiTreeNode));
tr->data=data;
tr->left = CreateBSTree();
tr->right = CreateBSTree();

return tr;
}
}
//中序遍历二叉树
void InOrderTraverse(BiTreeNode * root)
{
if(root->left)
InOrderTraverse(root->left);

if(root)
printf("%d ",root->data);

if(root->right)
InOrderTraverse(root->right);
}
void printPath(int path[],int top)
{
printf("第一组:");
for(int i=0;i<top;i++)
printf("%d ",path[i]);
printf("\n");
}
void findPath(BiTreeNode *root, int sum,int top,int path[])
{
path[top++] = root->data;
sum -= root->data;

if (root->left == NULL && root->right==NULL)
{
if (sum == 0)
{
printPath(path, top);
}
}
else
{
if (root->left != NULL)
findPath(root->left, sum, top,path);
if (root->right!=NULL)
findPath(root->right, sum, top,path);
}
top --;
sum += root->data;
}
int main()
{
freopen("input.txt","r",stdin);

BiTreeNode * root=CreateBSTree();

InOrderTraverse(root);
printf("\n");

int sum=22;
int top=0;
//scanf("%d",&sum);
int path[MAX]={0};
findPath(root,sum,top,path);

getchar();
return 0;
}

分享到:
评论

相关推荐

    微软等公司数据结构+算法面试100题(含答案)

    4.在二元树中找出和为某一值的所有路径(树) 题目:输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。 例如 输入整数22和如下...

    算法永远是王道(含微软面试100题)

    算法永远是王道(含微软面试100题) (把二元查找树转变成排序的双向链表;设计包含min函数的栈;求子数组的最大和;在二元树中找出和为某一值的所有路径;查找最小的k个元素等)

    C/C++程序员面试指南.杨国祥(带详细书签).pdf

    面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现直接插入排序 面试题2:编码实现希尔(Shell)排序 11.2 交换排序 面试题3:编码实现冒泡排序 面试题4:编码实现快速...

    数据结构关于迷宫问题

    要求设计程序输出如下:...(2)找出一条通路的二元组(i,j)数据序列,(i,j)表示通路上某一点的坐标。 (3)用一种标志(如数字8)在迷宫中标出该条通路; (4)在屏幕上输出迷宫和通路; (5)上述功能可用菜单选择

    Facebook AI实验室开源的相似性搜索库Faiss.zip

    找出在城市规模、生活成本和便利设施方面相似的城市后,她便可以查看这些城市的薪资水平,从而确定它们是否与本公司的薪资水平一致。犯罪分析师希望搜索数据库以查看某罪行是否属于较重犯罪形式或有重罪趋势。课外...

    算法面试题500

    1.2.5. 在二元树中找出和为某一值的所有路径 .............................................. 22 1.2.6. Top K 算法详细解析---百度面试 ......................................................... 29 1.2.7. ...

    世界500强面试题.pdf

    1.2.5. 在二元树中找出和为某一值的所有路径 .............................................. 22 1.2.6. Top K 算法详细解析---百度面试 ......................................................... 29 1.2.7. ...

    LINGO软件的学习

    在LINGO中,只有在初始部分中给出的集属性值在以后的求解中可更改。这与前面并不矛盾,初始部分是LINGO求解器的需要,并不是描述问题所必须的。 2.3.2 定义派生集 为了定义一个派生集,必须详细声明: •集的名字 •...

    leetcode1185-LeetCode:这是我的LeetCode解决方案和笔记的笔记本

    找出两个数组之间的距离值 #1337. 矩阵中最弱的 K 行 #15. 3Sum(前指针和后指针) #347. 前 K 个频繁元素(堆) #203. 删除链表元素 动态规划 #1043. 最大和的分区数组 #264. 丑二号(万能DP) 搜索 #275. H-Index ...

    DS_ALGO:数据结构和算法

    找出a,b使a + b = X 合并后找到两个排序数组的中位数 图算法 图表示 广度优先搜索 深度优先搜索 拓扑排序 未加权图的最小路径 有向无环图的最短路径 Dijkstra的算法 Floyd Warshall算法 递归 河内塔 N皇后问题 ...

Global site tag (gtag.js) - Google Analytics