My recursive O(n) solution

• ``````public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
if(root != null)
binaryTreePaths(root,paths, "");
return paths;
}
public void binaryTreePaths(TreeNode root, List<String> paths, String path) {
StringBuilder pathb = new StringBuilder(path);
pathb.append(root.val);
if(root.left == null && root.right == null) {
return;
} else {
pathb.append("->");
String curPath = pathb.toString();
if(root.left != null) binaryTreePaths(root.left, paths, curPath);
if(root.right != null) binaryTreePaths(root.right,paths, curPath);
}
}
``````

}

• In your "O(n)", what is n?

• ``````public class Solution {

public List<String> binaryTreePaths(TreeNode root) {
List<String> list = new ArrayList<>();
if (root == null)   return list;
getPaths(root, list, new StringBuilder());
return list;
}

private void getPaths(TreeNode root, List<String> list, StringBuilder sb) {
if (root != null) {
if (root.left == null && root.right == null) {
} else {
if (root.left != null) {
getPaths(root.left, list, sb.append(root.val).append("->"));
sb.delete(sb.lastIndexOf(String.valueOf(root.val)), sb.length());
}
if (root.right != null) {
getPaths(root.right, list, sb.append(root.val).append("->"));
sb.delete(sb.lastIndexOf(String.valueOf(root.val)), sb.length());
}
}
}
}
``````

• This is very similar to the above solution with a DFS style traversal with O(n) and n refers to number of nodes in the tree.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.