C++ 4ms solution, BFS


  • 0
    vector<vector<int>> zigzagLevelOrder(TreeNode* rt)
    {
    	vector<vector<int>> ret;
    	if (!rt)
    		return ret;
    	vector<int> path;
    	vector<TreeNode*> q; //vector can be replaced by queue<TreeNode*> q
    	q.push_back(rt);
    	q.push_back(0); //set '0' as the separator of layer.
    	int dir = 1; //direction indice. dir==1: left->right; dir==0: right->left
    	while (!q.empty())
    	{
    		TreeNode *t = q.front();
    		q.erase(q.begin());
    		if (t)
    		{
    			if (dir)
    				path.push_back(t->val);
    			else //dir==0
    				path.insert(path.begin(), t->val); //insert the 'val' into head of 'path'
    			if (t->left)
    				q.push_back(t->left);
    			if (t->right)
    				q.push_back(t->right);
    		}
    		else if (!q.empty())
    		{
    			ret.push_back(path);
    			path.clear();
    			q.push_back(0);
    			dir = !dir; //change the direction
    		}
    	}
    	ret.push_back(path);
    	return ret;
    }

Log in to reply
 

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