题目(二叉树中和为某一值的路径—牛客网)

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

算法思路

首先，处理根节点为空的情况；

接下来，按照前序遍历的思想从根节点开始递归搜索，每次先将节点加入路径，然后更新期望的路径和，即减去当前已加入路径的节点值,利用数组 path 存放当前已加入路径的节点值，然后依次判断根节点的左右子树是否存在，存在则继续递归寻找，待递归返回后，必须从路径中移除当前节点，以便继续记录其余路径；

最后，就是递归出口。当遇到了叶节点，并且叶节点的值刚好等于剩余期望的路径和，那么就找到了一条路径；最后依然要从路径中移除当前节点，以便继续记录其余路径，最后再返回。

算法实现

复杂度分析

算法遍历了每个节点，时间复杂度为 O(n)，空间复杂度主要在递归栈，大致消耗 O(logn)的空间,还有一些辅助数组空间。

参考

<<剑指offer2>>