在二叉树中找出和为某一值的所有路径

题目:输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。

例如:

10
/     \
5       12
/ \
4   7

输入整数22,输出如下路径:

10  12
10  5  7

解:就是最简单的先序遍历,只不过要记录路径,可以使用数组,我这里用的stl::vector。

注意left和right遍历后,要回退当前结点在path中状态。

算法:

其他树定义,创建等的实现如下:

Leave a Reply

Your email address will not be published.