My 4ms solution based on level order traversal


  • 3
    S
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    		vector<vector<int>> ret;
    		if (root == NULL)	return ret;
    		queue<TreeNode*> queue;
    		queue.push(root);
    		int i = 0;
    
    		while (!queue.empty()){
    			vector<int> subret;
    			int ssize = queue.size();
    			while (ssize--){
    				root = queue.front();
    				queue.pop();
    				subret.push_back(root->val);
    				if (root->left != NULL)	queue.push(root->left);
    				if (root->right != NULL)queue.push(root->right);
    			}
    			if (i++ % 2 == 1)
    				reverse(subret.begin(), subret.end());
    			ret.push_back(subret);
    		}
    
    		return ret;
    	}

Log in to reply
 

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