# 257.Binary-Tree-Paths

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/binary-tree-paths/

## ้ข็ฎๆ่ฟฐ

``````Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:
Input:

1
/   \
2     3
\
5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3``````

## ไปฃ็ 

### Approach #1 Recursion

Time `O(N)` Space `O(N)`

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
dfs(root, "", paths);
return paths;
}

private void dfs(TreeNode root, String path, LinkedList<String> paths) {
if (root != null) {
path += Integer.toString(root.val);
if (root.left == null && root.right == null) {
} else {
path += "->";
dfs(root.left, path, paths);
dfs(root.right, path, paths);
}
} else {
// stop dfs
}
}
}``````

### Approach #2 DFS Iteration + Two Stack

``````class Solution {
public List<String> binaryTreePaths(TreeNode root) {
if (root == null)  return paths;

TreeNode node;
String path;
while ( !node_stack.isEmpty() ) {
node = node_stack.pollLast();
path = path_stack.pollLast();
if ((node.left == null) && (node.right == null))
if (node.left != null) {