Clear C++ Iterative Solution with 2 Stack


  • 0
    B
    • Use 2 stacks, one for the current level, one for the next level.
    • If current level is even then push the children to the stack by left-to-right order.
    • If current level is odd then push the children to the stack by right-to-left order.

    Here is the solution:

    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
            vector<vector<int> > ret;
            vector<int> sub;
            stack<TreeNode*> s[2];
            int lvl = 0;
            
            if (root == NULL)
                return ret;
                
            s[lvl].push(root);
            
            while(!s[0].empty() || !s[1].empty()) {
                while(!s[lvl].empty()) {
                    TreeNode *node = s[lvl].top();
                    s[lvl].pop();
                    
                    if (node == NULL) continue;
                    
                    sub.push_back(node->val);
                    if (lvl % 2 == 0) {
                        s[(lvl + 1) % 2].push(node->left);
                        s[(lvl + 1) % 2].push(node->right);
                    }
                    else {
                        s[(lvl + 1) % 2].push(node->right);
                        s[(lvl + 1) % 2].push(node->left);
                    }
                }
                if (sub.size() > 0)
                    ret.push_back(sub);
                sub.clear();
                
                lvl = (lvl + 1) % 2;
            }
            return ret;
        }

  • 0
    B

    Similar Idea as you.

    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
    	vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
    		vector<vector<int> > res;
    		if (root == NULL)
    			return res;
    
    		stack<TreeNode*> nodes;
    		nodes.push(root);
    		bool left_to_right = true;
    		while (!nodes.empty()) {
    			stack<TreeNode*> next_nodes;
    			vector<int> cur_values;
    			while (!nodes.empty()) {
    				TreeNode *cur_node = nodes.top();
    				nodes.pop();
    				if (cur_node == NULL)
    					continue;
    				cur_values.push_back(cur_node->val);
    				if (left_to_right) {
    					next_nodes.push(cur_node->left);
    					next_nodes.push(cur_node->right);
    				} else {
    					next_nodes.push(cur_node->right);
    					next_nodes.push(cur_node->left);
    				}
    			}
    			if (!cur_values.empty())
    				res.push_back(cur_values);
    			nodes = next_nodes;
    			left_to_right = !left_to_right;
    		}
    		return res;
    	}
    };

Log in to reply
 

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