3.10  如何在二叉树中找出与输入整数相等的所有路径

3.10 如何在二叉树中找出与输入整数相等的所有路径

【出自BD面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

从树的根结点开始往下访问一直到叶子结点经过的所有结点形成一条路径。找出所有的这些路径，使其满足这条路径上所有结点数据的和等于给定的整数。例如：给定如下二叉树与整数8，满足条件的路径为6-＞3-＞-1（6+3-1=8）。

分析与解答：

可以通过对二叉树的遍历找出所有的路径，然后判断各条路径上所有结点的值的和是否与给定的整数相等，如果相等，则打印出这条路径。具体实现方法可以通过对二叉树进行先序遍历来实现，实现思路为对二叉树进行先序遍历，把遍历的路径记录下来，当遍历到叶子结点时，判断当前的路径上所有结点数据的和是否等于给定的整数，如果相等则输出路径信息，示例代码如下：

程序的运行结果如下：

满足路径结点和等于8的路径为：63-1

算法性能分析：

这种方法与二叉树的先序遍历有着相同的时间复杂度O（N），此外，这种方法用一个数组存放遍历路径上结点的值，在最坏的情况下时间复杂度为O（N）（所有结点只有左子树，或所有结点只有右子树），因此，空间复杂度为O（N）。