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

• 算法与数据结构
• 2020-10-09 16:38:03

题目：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。（题目来自剑指Offer）

实例：

解法：递归

/**
 * @desc 二叉树中和为某一值的路径
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
let pathSum = function(root, sum) {
  if (!root) return [];
  let res = [];
  let _pathSun = (root, sum, path) => {
    if (!root) return;
    path = [...path, root.val]; //浅拷贝
    // 无左右节点说明已经为1条路径，sum等于叶子节点的值说明sum为该路径的值。
    if (!root.left && !root.right && sum === root.val) { 
      res.push(path);
      return;
    }
    _pathSun(root.left, sum - root.val, path); 
    _pathSun(root.right, sum - root.val, path);
  };
  _pathSun(root, sum, []);
  return res;
};