✅113. 路径总和 II

[Ray-56]

113. 路径总和 II

题目

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

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

示例：

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

       5
      / \
    4    8
   /    /  \
  11   13   4
 /  \     /  \
7    2   5    1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

[Ray-56]

dfs解

var pathSum = function(root, sum) {
    let ret = [];
    if (!root) return ret;
    let path = [];
    dfs(root, sum, path, ret);
    return ret;
};

function dfs(node, sum, path, ret) {
    if (node === null) return;

    // 这里是判断叶子节点
    if (node.left === null && node.right === null && node.val === sum) {
        ret.push(path.concat([node.val]));
        return;
    }

    if (node.left !== null) {
        dfs(node.left, sum - node.val, path.concat([node.val]), ret);
    }

    if (node.right !== null) {
        dfs(node.right, sum - node.val, path.concat([node.val]), ret);
    }
}