344-Leetcode 二叉树的所有路径

算法：我们也可以用广度优先搜索来实现。我们维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，如果它是叶子节点，则将它对应的路径加入到答案中。如果它不是叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜索结束，我们即能得到答案

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;
}

时间复杂度：O(N ^ 2)，其中 N 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(N)，故时间复杂度为 O(N^2)
空间复杂度：O(N ^ 2)，其中 N 表示节点数目。在最坏情况下，队列中会存在 N 个节点，保存字符串的队列中每个节点的最大长度为 N，故空间复杂度为 O(N^2)