All paths of 344 leetcode binary tree

Algorithm ： We can also use breadth first search to achieve . We maintain a queue , Storage node and the path from the root to the node . At first, there was only the root node in the queue . In each iteration , We take out the first node in the queue , If it's a leaf node , Then add its corresponding path to the answer . If it's not a leaf node , Then all its child nodes are added to the end of the queue . When the queue is empty, the breadth first search ends , We can get the answer

struct TreeNode
{
    
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {
    }
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {
    }
};
class Solution
{
    
public:
	vector<string> binaryTreePaths(TreeNode* root)
	{
    
		vector<string> paths;
		if (root == nullptr) return paths;

		queue<TreeNode*> node_queue;
		queue<string> path_queue;
		node_queue.push(root);
		path_queue.push(to_string(root->val));

		while (!node_queue.empty())
		{
    
			TreeNode* t = node_queue.front(); node_queue.pop();
			string path = path_queue.front(); path_queue.pop();
			if (t->left == nullptr && t->right == nullptr)
			{
    
				paths.push_back(path);		
			}
			else
			{
    
				if (t->left != nullptr)
				{
    
					node_queue.push(t->left);
					path_queue.push(path + "->" + to_string(t->left->val));
				}
				if (t->right != nullptr)
				{
    
					node_queue.push(t->right);
					path_queue.push(path + "->" + to_string(t->right->val));
				}
			}
		}
		return paths;
	}
};
int main()
{
    
	Solution A;
	TreeNode* t = new TreeNode(1, new TreeNode(2, nullptr, new TreeNode(5, nullptr, nullptr)), new TreeNode(3, nullptr, nullptr));
	vector<string> vs = A.binaryTreePaths(t);
	for (auto& x : vs)
	{
    
		cout << x << endl;
	}
	return 0;
}

Time complexity ：O(N ^ 2), among N Indicates the number of nodes . In depth first search, each node will be accessed once and only once , Every time, it will be right path Variable to copy and construct , The cost of time is O(N), So the time complexity is O(N^2)
Spatial complexity ：O(N ^ 2), among N Indicates the number of nodes . In the worst case , There will be in the queue N Nodes , The maximum length of each node in the queue where the string is saved is N, So the complexity of space is O(N^2)