Using a count to mark the level we can slove this with Level Order Traversal easily


  • 0
    S

    1.this problem is similarity with Binary Tree Level Order Traversal ,we can add a count to mark the level
    2.when level % 2 == 0,we reverse the number in the vector,then push them into the vector result.other else we push them into the vector straightly.

    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> result;
    		queue<TreeNode *> q;
    		if (!root)
    		{
    			return result;
    		}
    		q.push(root);
    		q.push(NULL);
    		vector<int> cur;
    		int level = 1;
    		while (!q.empty())
    		{
    			TreeNode* t = q.front();
    			q.pop();
    			if (t == NULL)
    			{
    				if (level % 2 == 0)
    				{
    					reverse(cur.begin(), cur.end());
    				}
    				result.push_back(cur);
    				cur.resize(0);
    				if (q.size() > 0)
    				{
    					q.push(NULL);
    				}
    				level++;
    			}
    			else
    			{
    				cur.push_back(t->val);
    				if (t->left)
    				{
    					q.push(t->left);
    				}	
    				if (t->right)
    				{
    					q.push(t->right);
    				}
    			}
    		}
    		return result;
        }
    };
    

Log in to reply
 

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