一天一大 lee(二叉树的所有路径)难度:简单-Day20200904

输入:

   1
 /   \
2     3
 \
  5

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

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
  let _result = []
  function dfs(node, path) {
    if (!node) return
    path += node.val.toString()
    if (node.left === null && node.right === null) {
      // 当前节点是叶子节点
      _result.push(path) // 把路径加入到答案中
    } else {
      path += '->' // 当前节点不是叶子节点，继续递归遍历
      dfs(node.left, path)
      dfs(node.right, path)
    }
  }
  dfs(root, '')
  return _result
}

var binaryTreePaths = function (root) {
  let _result = []
  if (root === null) return _result
  let node_queue = [root],
    path_queue = [root.val.toString()]

  while (node_queue.length) {
    let node = node_queue.shift(),
      path = path_queue.shift()

    if (node.left === null && node.right === null) {
      _result.push(path)
    } else {
      if (node.left !== null) {
        node_queue.push(node.left)
        path_queue.push(path + '->' + node.left.val.toString())
      }

      if (node.right !== null) {
        node_queue.push(node.right)
        path_queue.push(path + '->' + node.right.val.toString())
      }
    }
  }
  return _result
}