C++ solution using only one queue / use a marker NULL


  • 88
    P
    class Solution {
    public:
        vector<vector<int> > levelOrder(TreeNode *root) {
            vector<vector<int> >  result;
            if (!root) return result;
            queue<TreeNode*> q;
            q.push(root);
            q.push(NULL);
            vector<int> cur_vec;
            while(!q.empty()) {
                TreeNode* t = q.front();
                q.pop();
                if (t==NULL) {
                    result.push_back(cur_vec);
                    cur_vec.resize(0);
                    if (q.size() > 0) {
                        q.push(NULL);
                    }
                } else {
                    cur_vec.push_back(t->val);
                    if (t->left) q.push(t->left);
                    if (t->right) q.push(t->right);
                }
            }
            return result;
        }
    };

  • 0
    F

    brilliant! . . . . . . . . .


  • 0
    L

    very nice answer ................................


  • 0
    M

    Awesome!!! it is so simple :)


  • 0
    P
    This post is deleted!

  • 0
    P
    This post is deleted!

  • 0
    F

    Can I ask why push_back(cur_vec) when t==NULL? I understand that for each level cur_vec needs to be push_back in the result. But it does not seem to me that the path terminator in the binary tree serialization is equivalent to the end of the current level? Am I missing something? thanks.


  • 0
    S

    brilliant:-)


  • 4
    X

    @pankit why not

    vector<vector<int>> levelOrder1(TreeNode* root) {
    		vector<vector<int>> res;
    		if (!root)
    			return res;
    		queue<TreeNode*> level_node;
    		level_node.push(root);
    		while (!level_node.empty()) {
    			vector<int> level_val;
    			auto sz = level_node.size();
    			for (decltype(sz) i = 0; i < sz; ++i) {
    				TreeNode *node = level_node.front();
    				level_node.pop();
    				level_val.push_back(node->val);
    				if (node->left)
    					level_node.push(node->left);
    				if (node->right)
    					level_node.push(node->right);
    			}
    			res.push_back(level_val);
    		}
    		return res;
    	}
    

  • 0
    W

    @pankit very clever!


  • 0
    L

    @xiaonimo Agree. It is unnecessary to insert a NULL to keep track of the end of every level.


  • 0
    A

    @xiaonimo @leetdn

    I think the advantage of using NULL as sentinel of end of level here is you can forget about the size of elements in queue or you don't need to count how many node you visited in this level to detect the end of each level. Getting a single NULL means you reach the end of each level; getting 2 consequent NULLs means you finish the traversal.

    class Solution {
    public:
    vector<vector<int> > levelOrder(TreeNode *root) {
    vector<vector<int> > res;
    vector<int> line;
    TreeNode *prev = NULL, *curr = NULL;

        queue<TreeNode*> Q;
        Q.push(root);
        Q.push(NULL);
        
        while (true) {
            curr = Q.front();
            Q.pop();
    
            if (NULL != prev) {
                line.push_back(prev->val);
            }
            
            if (NULL == curr) {
                if (NULL == prev) {
                    // Traversal completed.
                    break;
                } else {
                    // Reaches the end of each level.
                    Q.push(NULL);
                    res.push_back(line);
                    line.clear();
                }
    
            } else {
                if (curr->left) {
                    Q.push(curr->left);
                }
                
                if (curr->right) {
                    Q.push(curr->right);
                }
            }
            
            prev = curr;
        }
        
        return res;
    }
    

    };


  • 0
    S

    Same idea with C++ 11.

    vector<vector<int>> levelOrder(TreeNode* root) {
            std::vector<std::vector<int>> values;
            if (root == nullptr)
                return values;
            std::queue<TreeNode*> q;
            q.push(root);
            q.push(nullptr); // a flag indicating the end of a level
            values.push_back(std::vector<int>());
            while (true){
                auto p = q.front();
                q.pop();
                if (p == nullptr){ // a level is finished
                    if (q.empty()) // no more levels, ending of the tree
                        break;
                    q.push(nullptr); // the ith level is poped completely, then we can add the nullptr for the (i+1)th level
                    values.push_back(std::vector<int>()); // to store the values of the next level
                }else{
                    values.back().push_back(p->val);
                    if (p->left != nullptr)
                        q.push(p->left);
                    if (p->right != nullptr)
                        q.push(p->right);
                }
            }
            return values;
        }
    

  • 0
    W

    nice solution!


  • 0
    E

    @faustlin consider NULL as a mark which indicates a level ends here. Every time you meet a NULL, you must have put the nodes of this level into the vector, and all the children of them into the queue. So here cur_vec has all nodes of this level and you need to store it in result. Then you put another NULL into the queue to mark the end of the next level.


  • 0
    H

    My 3ms solution use deque.

    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> ret;
            if (root == NULL){
                return ret;
            }
            deque<TreeNode*> q;
            q.push_back(root);
            int next = 1;  //record how many elements should be poped in next level
            while(1){
                vector<int> v;
                int cflag = 0;
                int nnext = 0;
                int qsize = q.size();
                
                for(int i = 0; i < qsize; i++){
                    if(q[i] != NULL){  //if all elements in queue are null, break;
                        cflag = 1;
                }
                
                if(cflag == 1){
                    for(int i = 0; i < next; i++){
                        TreeNode * f = q.front(); 
                        if(f != NULL){
                            v.push_back(f->val);
                            q.pop_front();
                            q.push_back(f->left);
                            q.push_back(f->right);
                            nnext += 2;
                        }else{
                            q.pop_front();
                        }
                    }
                }else{
                    break;
                }
                
                ret.push_back(v);
                next = nnext;
            }
            return ret;
        }
    };
    

Log in to reply
 

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