Solution
The solution is straightforward and the given function can be called recursively without using any other helper function.
vector<string> binaryTreePaths(TreeNode* root) {
if (!root)
return {};
vector<string> left, right, res;
left = binaryTreePaths(root->left);
right = binaryTreePaths(root->right);
for (string s : left) {
res.push_back(to_string(root->val)+"->"+s);
}
for (string s : right) {
res.push_back(to_string(root->val)+"->"+s);
}
if (res.size()==0)
res={to_string(root->val)};
return res;
}
Note that the time complexity is not O(n) as string concatenation takes up a lot of time. It will take more time that O(n). Some people have argued that it is O(nlogn). O(n^2) is definitely a correct bound though it might not be a tight bound.