Simple solution using two stacks


  • 2
    N
    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
           vector<vector<int> > results;
    		if (root == NULL)
    			return results;
    		stack<TreeNode*> s1;
    		s1.push(root);
    		stack<TreeNode*> s2;
    		stack<TreeNode*> *cur = &s1;
    		vector<int> result;
    		while (!s1.empty() || !s2.empty()) {
    			if (cur == &s1) {
    				TreeNode *tmp = s1.top();
    				s1.pop();
    				result.push_back(tmp->val);
    				if (tmp->left != NULL)
    					s2.push(tmp->left);
    				if (tmp->right != NULL)
    					s2.push(tmp->right);
    				if (s1.empty()) {
    					results.push_back(result);
    					result.clear();
    					cur = &s2;
    				}
    
    			} else {
    				TreeNode *tmp = s2.top();
    				s2.pop();
    				result.push_back(tmp->val);
    				if (tmp->right != NULL)
    					s1.push(tmp->right);
    				if (tmp->left != NULL)
    					s1.push(tmp->left);
    				if (s2.empty()) {
    					results.push_back(result);
    					result.clear();
    					cur = &s1;
    				}
    
    			}
    		}
    		return results;
        }
    };

Log in to reply
 

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