Contents

# 257. Binary Tree Paths

## 題目 :

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

### Example :

Note

Example 1:

Input: root = [1,2,3,null,5] Output: [“1->2->5”,“1->3”]

Example 2:

Input: root = [1] Output: [“1”]

#### 解題思路 :

• 這題可以使用DFS(Depth First Search)的概念，優先去走到最底，之後再回頭，前往另一個最底
• 這題用recursive的方式很好做

### Recursive解法

• time complexity: O(n) , space complexity: O(1)

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

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ import ( "strconv" ) func binaryTreePaths(root *TreeNode) []string { var res []string str := strconv.Itoa(root.Val) var findPath func(*TreeNode, string) findPath = func(node *TreeNode, str string) { if str != strconv.Itoa(node.Val) { str = str + "->" + strconv.Itoa(node.Val) } if node.Left != nil { findPath(node.Left, str) } if node.Right != nil { findPath(node.Right, str) } if node.Left == nil && node.Right == nil { res = append(res, str) } } findPath(root, str) return res } ``````