[Algorithm]Get Paths with Given Sum in Binary Tree

根据target得到所有path，path可以在任意一个节点开始和结束。和path with max sum类似，不过我们每次递归要返回的是子树里的所有path，为了避免不必要的计算，我们发挥所有path的时候也同时返回所有对应path的sum，所以我们新定义一个类result。在一个节点的时候，我们先递归左子树和右子树找到左子树和右子树中的的所有path，然后进行一下三种操作：

• 首先看当前node.val是不是等于target，如果是的话，当前node加入结果集，path只有当前node
• 然后看当前node和左子树return回来的每一条path能不能组成sum == target的path，能的话加入结果集
• 当前node和右子树return回来的每一条path能不能组成sum == target的path，能的话加入结果集
• 最后看左子树的每一条path和右子树的每一条path和当前node能不能组成sum == target的path，能的话加入结果集

不考虑加入结果集的时间，由于return回来的子树的path数为O(N^2)，因为两个node可以决定一条path，前三个都可以在O(N^2)时间完成，最后一步归根到底就是Two Sum的问题，也可以在O(N^2)时间完成。加入结果的时间取决于结果的多少k，path长度O(log n)，所以加入结果集的时间为O(k log n)。

最后注意把左边所有path右边path和当前node merge一下，return所有已当前node为root的subtree的所有path，记得加上当前node自己。这一步也是O(N^2)的，所以T(N) = 2T(N/2) + O(N^2)，根据master theorem，时间复杂度为O(N^2)。计算所需要的空间，所有path数量是N^2，因为两个node可以决定一条path，path的长度是O(log N)，所以空间复杂度是O(N^2 * log N)，代码如下：