113. 路径总和 II

[wengzc]

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

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

示例:

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

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

返回:

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

题目链接：https://leetcode-cn.com/problems/path-sum-ii

[wengzc]

思路分析：二叉树回溯法

详细版（便于理解）

/**
 * 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) {
    if (!root) return []
    let res = []
    let cur = []
    cur.push(root.val)
    helper(root, sum)
    return res
    function helper(root, sum) {
        if (!root.left && !root.right && sum === root.val) {
            res.push(cur.slice())
            return
        }
        if (root.left) {
            cur.push(root.left.val)
            helper(root.left, sum - root.val)
            cur.pop()
        }
        if (root.right) {
            cur.push(root.right.val)
            helper(root.right, sum - root.val)
            cur.pop()
        }
    }
};

精简版

// 精简版
var pathSum = function (root, sum) {
    let res = []
    let cur = []
    helper(root, sum)
    return res
    function helper(root, sum) {
        if (!root) return
        cur.push(root.val)
        if (!root.left && !root.right && sum === root.val) {
            res.push(cur.slice())
            // 这里不能加 return ，因为要 cur.pop()
        }
        helper(root.left, sum - root.val)
        helper(root.right, sum - root.val)
        // 遍历完左右节点，把 root.val 值 pop()出来
        cur.pop();
    }
};