113.路径总和II

链接：113.路径总和II
难度：Medium
标签：树、深度优先搜索、回溯、二叉树
简介：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

题解 1 - typescript

• 编辑时间：2020-09-26
• 执行用时：124ms
• 内存消耗：47.1MB
• 编程语言：typescript
• 解法介绍：递归调用。

function pathSum(root: TreeNode | null, sum: number): number[][] {
  if (root === null) return [];
  const val = root.val;
  if (val === sum && root.left === null && root.right === null) return [[val]];
  const nextSum = sum - val;
  const ans: number[][] = [];
  ans.push(...pathSum(root.left, nextSum).map(v => [val, ...v]));
  ans.push(...pathSum(root.right, nextSum).map(v => [val, ...v]));
  return ans;
}