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


  • 87
    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!


Log in to reply
 

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