Python求解二叉树路径问题时为何''.join()比字符串拼接慢很多

你遇到的性能差异本质是不同操作的适用场景差异，和你之前看到的结论不冲突，只是适用场景不同：

1. 大家常说的「字符串拼接远慢于join()」是有前提的，仅针对大量、反复拼接长字符串的场景，比如循环上千次每次拼接长度几十以上的字符串，这个结论才成立，你的场景刚好不在这个范围内。
2. 性能差异的核心开销在BFS遍历阶段：

• 列表存储路径的版本，每次生成子节点路径时执行path + ['L']，需要创建全新的列表对象，复制原有路径的所有元素再追加新字符。列表本身要存储每个元素的指针、长度、容量等元数据，内存开销远大于同内容的字符串，反复复制的累积成本非常高。
• 字符串存储路径的版本，CPython对单个字符的追加拼接做了底层优化，会预分配字符串的内存空间，实际复制开销比列表小得多。加上字符串是紧凑存储的结构，队列存取的额外开销也更低。

3. 最终结果生成阶段也有额外开销差：

• 列表版本需要先生成['U']*n的列表，再和目标路径剩余的列表拼接，最后还要调用join转成字符串，多了两次列表创建和一次全量遍历的开销。
• 字符串版本直接用'U'*n生成对应长度的字符串，直接和目标路径剩余部分拼接，所有操作都是底层C实现，没有额外类型转换开销。

对于你当前二叉树节点最多10万的场景，上述累积的开销差就会体现为好几秒的运行时间差距。

内容的提问来源于stack exchange，提问作者azi