二叉树的所有路径-257

[sl1673495]

给定一个二叉树，返回所有从根节点到叶子节点的路径。

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

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

给递归函数传递一个 path 数组，记录当前位置已经走过的节点，如果是叶子节点的话，就可以往全局的 res 结果数组里增加一个结果。

let binaryTreePaths = function (root) {
  let res = []
  let dfs = (node, path = "") => {
    if (!node) {
      return
    }

    let newPath = path ? `${path}->${node.val}` : `${node.val}`
    if (!node.left && !node.right) {
      res.push(newPath)
    }

    dfs(node.left, newPath)
    dfs(node.right, newPath)
  }
  dfs(root)
  return res
}

bobo 老师解法

用当前节点的值去拼接左右子树递归调用当前函数获得的所有路径。

也就是根节点拼上以左子树为根节点得到的路径，加上根节点拼上以右子树为根节点得到的所有路径。

直到叶子节点，仅仅返回包含当前节点的值的数组。

let binaryTreePaths = function (root) {
  let res = []
  if (!root) {
    return res
  }

  if (!root.left && !root.right) {
    return [`${root.val}`]
  }

  let leftPaths = binaryTreePaths(root.left)
  let rightPaths = binaryTreePaths(root.right)

  leftPaths.forEach((leftPath) => {
    res.push(`${root.val}->${leftPath}`)
  })
  rightPaths.forEach((rightPath) => {
    res.push(`${root.val}->${rightPath}`)
  })

  return res
}

[vortesnail]

var binaryTreePaths = function (root) {
  const res = [];

  var dfs = function (node, curPath) {
    if (!node) return;
    curPath.push(node.val);

    if (!node.left && !node.right) {
      res.push(curPath.slice().join('->'));
    }

    dfs(node.left, curPath);
    dfs(node.right, curPath);

    curPath.pop();
  }

  dfs(root, []);
  return res;
};