257. Binary Tree Paths
1. Description
Given a binary tree, return all root-to-leaf paths.
2. Note
- A leaf is a node with no children.
3. Example
Example 1:
Output: [“1->2->5”, “1->3”]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3
4. Solutions
My Accepted Solution
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(1)
// we could also use level traversal and non recursive depth-first search
// we could also pass the string by reference, but it is more tedious, especially we have to add "->"
class Solution
{
private:
vector<string> result;
void traverse(TreeNode *i_root, string path)
{
path += string("->") + to_string(i_root->val);
if(!i_root->left && !i_root->right) result.push_back(path);
if(i_root->left) traverse(i_root->left, path);
if(i_root->right) traverse(i_root->right, path);
}
public:
// vector<string> binaryTreePaths(TreeNode* root)
vector<string> binaryTreePaths(TreeNode *i_root)
{
if(!i_root) return vector<string>{};
string path = to_string(i_root->val);
if(i_root->left) traverse(i_root->left, path);
if(i_root->right) traverse(i_root->right, path);
if(!i_root->left && !i_root->right) result.push_back(path);
return result;
}
};