75 - 二叉树的所有路径

题目

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

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

示例:

输入:

1 / 2 3 5

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

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

解答

就是深度优先遍历咯😳

递归

https://leetcode.com/problems/binary-tree-paths/discuss/68418/Recursive-JavaScript-solution

const getPaths = function (root, pre, result) {
  if (!root) {
    return
  }
  pre.push(root.val)
  if (!root.left && !root.right) {
    result.push(pre.join('->'))
  } else {
    getPaths(root.left, pre, result)
    getPaths(root.right, pre, result)
  }
  pre.pop()
}
var binaryTreePaths = function (root) {
  let result = []
  let pre = []
  getPaths(root, pre, result)
  return result
};

Runtime: 52 ms, faster than 93.47% of JavaScript online submissions for Binary Tree Paths.

Memory Usage: 34.6 MB, less than 50.00% of JavaScript online submissions for Binary Tree Paths.

用join可以避免每次push的时候都要转成string，而是在最后一起转了。感觉效率会更高一些

写go的时候一直忘记要把地址传进去，导致输出结果一直是空😂

func getPaths(root *TreeNode, path string, result *[]string) {
    if root == nil {
        return
    }
    path += strconv.Itoa(root.Val)
    if root.Left == nil && root.Right == nil {
        *result = append(*result, path)
        fmt.Println("result", result)
    } else {
        path += "->"
        getPaths(root.Left, path, result)
        getPaths(root.Right, path, result)
    }
}
func binaryTreePaths(root *TreeNode) []string {
    var result []string
    getPaths(root, "", &result)
    return result
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Binary Tree Paths.

Memory Usage: 2.5 MB, less than 100.00% of Go online submissions for Binary Tree Paths.

go里面没有js的join因此只能用字符串来拼接了。

迭代

题解的迭代是广度优先算法。。建一个栈，有几个分支维护多少个字符串

var binaryTreePaths = function (root) {
  if (!root) {
    return []
  }
  let nodeStack = [root]
  let resultStack = [root.val.toString()];
  result = []

  while (nodeStack.length > 0) {
    let node = nodeStack.pop()
    path = resultStack.pop()
    if (!node.left && !node.right) {
      result.push(path)
      continue
    }
    if (node.left) {
      nodeStack.push(node.left)
      resultStack.push(path + "->" + node.left.val.toString())
    }
    if (node.right) {
      nodeStack.push(node.right)
      resultStack.push(path + "->" + node.right.val.toString())
    }
  }
  return result
};

Runtime: 60 ms, faster than 56.58% of JavaScript online submissions for Binary Tree Paths.

Memory Usage: 34.7 MB, less than 50.00% of JavaScript online submissions for Binary Tree Paths.

就感觉。。一会推进一会推出的好麻烦啊。。