• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ans;
dfs(root, {}, ans);
return ans;
}

private:
void dfs(TreeNode* root, vector<string>&& path, vector<string>& ans) {
if (!root)
return;
if (!root->left && !root->right) {
ans.push_back(join(path) + to_string(root->val));
return;
}

path.push_back(to_string(root->val) + "->");
dfs(root->left, move(path), ans);
dfs(root->right, move(path), ans);
path.pop_back();
}

string join(const vector<string>& path) {
string joined;
for (const string& s : path)
joined += s;
return joined;
}
};
``````

## JAVA

``````class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> ans = new ArrayList<>();
dfs(root, new StringBuilder(), ans);
return ans;
}

private void dfs(TreeNode root, StringBuilder sb, List<String> ans) {
if (root == null)
return;
if (root.left == null && root.right == null) {
return;
}

final int length = sb.length();
dfs(root.left, sb.append(root.val).append("->"), ans);
sb.setLength(length);
dfs(root.right, sb.append(root.val).append("->"), ans);
sb.setLength(length);
}
}
``````

## Python

``````class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
ans = []

def dfs(root: Optional[TreeNode], path: List[str]) -> None:
if not root:
return
if not root.left and not root.right:
ans.append(''.join(path) + str(root.val))
return

path.append(str(root.val) + '->')
dfs(root.left, path)
dfs(root.right, path)
path.pop()

dfs(root, [])
return ans
``````