while (!q.empty()) { auto cur = q.front(); if (cur->left == nullptr && cur->right == nullptr && isLeftNode.front()) { sum += cur->val; } q.pop(); isLeftNode.pop();

if (cur->left != nullptr) { q.push(cur->left); isLeftNode.emplace(true); } if (cur->right != nullptr) { q.push(cur->right); isLeftNode.emplace(false); } }

return sum; } };

TC should be O(n) and SC should be O(n) in worst case, where n is node number.