算法：二叉树中和为某一值的路径

算法：二叉树中和为某一值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例1

• 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
• 输出：[[5,4,11,2],[5,8,4,5]]

提示

• 树中节点总数在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

方法：深度优先搜索

从根开始计算，到找到某个节点的解，深度优先搜索（回溯）采用“一直向下走，走不通就掉头”的思想，相当于采用了“先跟遍历”的方法来构造搜索树。

算法如下：

• 递归当前节点，如果当前节点为空，直接返回；
• 否则目标和递减，用于判断是否满足目标和；
• 把当前节点的值加入到每一个路径集合中；
• 当目标和递减到0并且当前节点没有子节点，说明满足条件，直接把当前路径集合“复制”（因为路径集合是动态的）到结果集合中；
• 递归遍历左/右子节点；
• 向上回溯，需要将当前节点从路径集合中移除；
• 递归遍历整个树节点完成后，返回结果集合；

代码如下：

复杂度分析

• 时间复杂度：O(n)，因为要先序遍历所有的节点。
• 空间复杂度：O(n)，最差的情况下，所有节点的都满足，即整个二叉树都存到结果集合中。

END

绳锯木断，水滴石穿，赠友人。