> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-06-2022-257.md).

# 01/06/2022 257

using stringBuilder and dfs

```
public List<String> binaryTreePaths(TreeNode root) {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    helper(res, root, sb);
    return res;
}

private void helper(List<String> res, TreeNode root, StringBuilder sb) {
    if(root == null) {
        return;
    }
    int len = sb.length();
    sb.append(root.val);
    if(root.left == null && root.right == null) {
        res.add(sb.toString());
    } else {
        sb.append("->");
        helper(res, root.left, sb);
        helper(res, root.right, sb);
    }
    sb.setLength(len);//backtracking
}
```

Divide and Conquer

```
    List<String> result = new ArrayList<>(); 
    if(root == null) return result;
    
    if(root.left == null && root.right == null){
        result.add("" + root.val);
    }
    
    List<String> leftpath = binaryTreePaths(root.left);
    List<String> rightpath =  binaryTreePaths(root.right);
    
    for(String path: leftpath){
        result.add(root.val + "->" + path);
    }
    
    for (String path: rightpath){
        result.add(root.val + "->" + path);
    }
    
    return result;
```

class Solution { public List binaryTreePaths(TreeNode root) { LinkedList paths = new LinkedList(); if (root == null) return paths;

```
LinkedList<TreeNode> node_stack = new LinkedList();
LinkedList<String> path_stack = new LinkedList();
node_stack.add(root);
path_stack.add(Integer.toString(root.val));
TreeNode node;
String path;
while ( !node_stack.isEmpty() ) {
  node = node_stack.pollLast();
  path = path_stack.pollLast();
  if ((node.left == null) && (node.right == null))
    paths.add(path);
  if (node.left != null) {
    node_stack.add(node.left);
    path_stack.add(path + "->" + Integer.toString(node.left.val));
  }
  if (node.right != null) {
    node_stack.add(node.right);
    path_stack.add(path + "->" + Integer.toString(node.right.val));
  }
}
return paths;
```

} }