sl1673495 / leetcode-javascript

:beers: 喝杯小酒,一起做题。前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label,一起加油。
2.08k stars 344 forks source link

二叉树的所有路径-257 #59

Open sl1673495 opened 4 years ago

sl1673495 commented 4 years ago

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

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

示例:

输入:

   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 commented 3 years ago
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;
};