算法练习10：二叉树中和为某值的路径（leetcode113）

leetcode113(剑指 Offer 34): 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

leetcode: https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

因为懒，所以先写一个树节点的构造函数，用前序遍历的方式遍历生成一棵树，不想一个个树节点手动创建。（当然手动在实现上更简单，不容易有错，建议在面试中手动创建=。=，不然容易添加翻车的机率）

生成的树长这个样子：

// 树节点的构造函数
function Tree(val) {
  this.val = val
  this.left = null
  this.right = null
}

const arr = [5,4,11,7,null,null,2,null,null,null,8,13,null,null,4,5,null,null,1,null,null]
// 构造一棵树
function getTree(arr) {
  if(!arr.length) reutrn;
  let data = arr.shift()
  let node = null
  if(data) {
    node = new Tree(data)
    node.left = getTree(arr)
    node.right = getTree(arr)
  }
  return node
}
const tree = getTree(arr)

先看题目，所求的路径，是从根节点出发，然后找到叶子节点的路径，从这句中，可以看出它是一个深层遍历，且从根节点出发，所以要使用前序遍历的方法。

所以，我们可以一步一步来

1. 先求出所有前序遍历的路径：

// 前序遍历，获取从根节点到叶子节点的所有路径
function getAllPath(tree, res, path) {
  if(!tree) return;
  path.push(tree.val)
  getAllPath(tree.left, res, path)
  getAllPath(tree.right, res, path)
  // 当左子节点和右子节点都为null时，才是叶子节点，此时记录好这条路径
  if(!tree.left && !tree.right) {
    // 注意，这里存入结果的是一条路径的拷贝，否则后续修改路径会影响到已经记录好的路径
    res.push([...path])
  }
  // 这里，是当遍历完一个节点的左右子节点后，回溯到它的父节点
  path.pop()
  return res;
}
const paths = getAllPath(tree, [], [])
console.log(paths)
// [ [ 5, 4, 11, 7 ],
  // [ 5, 4, 11, 2 ],
  // [ 5, 8, 13 ],
  // [ 5, 8, 4, 5 ],
  // [ 5, 8, 4, 1 ] ]

2. 那么要取得路径结果为target的路径，在此基础上，就很简单了
   • 每次将当前节点的值放入路径中path，然后记录target = target-当前值
   • 当到叶子节点时，判断target是否等于0，等于0说明当前路径就是我们要的路径，此时将路径保存到结果队列中
   • 当遍历完此节点左右子节点后，回溯遍历其父节点

function getSumPath(tree, target, res, path) {
  if(!tree) return;
  // target = target-当前节点值
  target -= tree.val
  // path记录当前节点
  path.push(tree.val)
  getSumPath(tree.left, target, res, path)
  getSumPath(tree.right, target, res, path)
  // 当target为0，代表到叶子节点的路径和刚好为target时，此时保存路径
  if(target === 0 && !tree.left && !tree.right) {
    // 注意，这里存入结果的是一条路径的拷贝，否则后续修改路径会影响到已经记录好的路径
    res.push([...path])
  }
  path.pop()
  return res;
}
// const targetPaths = getSumPath(tree, 22, [], [])
// console.log(targetPaths) // [ [ 5, 4, 11, 2 ], [ 5, 8, 4, 5 ] ]

// leetcode要求的外层函数
function getPaths(tree, target) {
  return getSumPath(tree, target, [], [])
}
console.log(getPaths(tree, 22));