C++11 style AC code


  • 0
    Z

    Traditionally we would use two queues, and use pointers to point to them so that we can efficiently swap to next level. Using C++11's specialized swap, we can do this in constant time. Also, use move operator to push the current level's content to result is very convenient.

    class Solution {
    public:
        vector<vector<int> > levelOrder(TreeNode *root) {
            vector<vector<int> > result;
            if (root == nullptr) return result;
            queue<TreeNode *> cur, nxt;
            cur.push(root);
            
            vector<int> buffer;
            while (!cur.empty()) {
                TreeNode *node = cur.front();
                cur.pop();
                buffer.push_back(node->val);
                if (node->left) {
                    nxt.push(node->left);
                }
                if (node->right) {
                    nxt.push(node->right);
                }
                if (cur.empty()) {
                    // awesome c++11 feature: constant swap
                    swap(cur, nxt);
                    // awesome c++11 feature: move instead of copy
                    result.push_back(move(buffer));
                    buffer.clear();
                }
            }
            
            return result;
        }
    };

  • 0
    J

    Why so serious? The basic STL utilities is good by default and you should not use std::move without careful consideration.

    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> result;
            if (root == NULL) return result;
            vector<TreeNode*> levelA = {root};
            vector<TreeNode*> levelB;
            vector<int> values;
            while (levelA.size() > 0) {
                for (int i = 0; i < levelA.size(); i++) {
                    TreeNode* node = levelA[i];
                    values.push_back(node->val);
                    if (node->left != NULL) levelB.push_back(node->left);
                    if (node->right != NULL) levelB.push_back(node->right);
                }
                result.push_back(values);
                swap(levelA, levelB);
                levelB.clear();
                values.clear();
            }
            return result;
        }
    };

  • 0
    J
    1. By default, std::queue use std::deque which contains a map for random element access as the internal underlying container. If you care about the instant memory occupation, you can use std::list instead.
    2. After std::moveing the buffer, the capacity of the buffer is 0. It means that you must do another round of reallocation while the maximum of TreeNodes on the level might not increase.

  • 0
    T

    It's possible using only one level. Either bulk-remove k elements after the for loop, where k is levelA.size() before the for loop; but better use a deque which promises constant time push_back and pop_front and can store [levelA, levelB] in one array, you know how big levelA is because at the beginning of the for loop no levelB items has been inserted.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.