1. 题目描述

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

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

  1.       5
  2.      / \
  3.     4   8
  4.    /   / \
  5.   11  13  4
  6.  /  \    / \
  7. 7    2  5   1

返回:

  1. [
  2.    [5,4,11,2],
  3.    [5,8,4,5]
  4. ]

2. 实现思路

可以使用深度优先遍历来实现：

  • 首先，遍历到节点时，将当前节点的值放入到一个数组中
  • 分别遍历左右子节点，遍历时sum将去当前值，就等于后面还需要相加的和
  • 如果当前节点没有左右子节点，并且当前节点的值与还需要相加的值相等，就将暂存路径值的数组arr的值保存到结果数组中

  • 最后不要忘了每次遍历完，将暂存路径节点的数组做出数组操作。以此进行回溯操作。

    3. 代码实现

    ```javascript /**

    • Definition for a binary tree node.
    • function TreeNode(val) {
    • this.val = val;
    • this.left = this.right = null;
    • } / /*
    • @param {TreeNode} root
    • @param {number} sum

    • @return {number[][]} */ var pathSum = function(root, sum) { let res = []

      fn(root, sum, res, []) return res };

function fn(root, sum, res, arr){ if(!root) return arr.push(root.val) // 当节点没有左右子树的时候，并且根节点等于当前的sum值时，就将当前路径的值保存在结果中 if(!root.left && !root.right && root.val === sum){ res.push([…arr]) } fn(root.left, sum - root.val, res, arr) fn(root.right, sum - root.val, res, arr) arr.pop() // 将当前节点出数组 } ```

4. 提交结果

113. 路径总和 II - 图1