我有以下工作代码(g ++ 8.2,C ++ 17标准。)
queue<TreeNode*> q{};
q.push(root);
q.push(nullptr);
int sum = root -> val;
while (!q.empty()) {
TreeNode *n = q.front();
q.pop();
if (n != nullptr) {
sum += n->val;
if (n-> left != nullptr) q.push(n->left);
if (n-> right != nullptr) q.push(n->right);
} else {
if (q.empty()) break;
q.push(nullptr);
sum = 0;
}
}
return sum;
然后我将queue<TreeNode*>
替换为deque<TreeNode*>
。事实证明,速度至少提高了20%。为什么deque<TreeNode*>
比queue<TreeNode*>
快得多?谢谢!
来自cppreference.com: std::queue
template<
class T,
class Container = std::deque<T>
> class queue;
Container
-用于存储元素的基础容器的类型。
因此std::queue
-默认情况下-使用std::deque
作为其内部容器,因此它最多只能与std::deque
一样快,但是因为它是包装器-取决于编译器可以执行的优化-较慢。