题目
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1 / 2 3 5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
解答
就是深度优先遍历咯😳
递归
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.
就感觉。。一会推进一会推出的好麻烦啊。。