검지offer-면접문제 61: 지그재그 순서로 두 갈래 나무 프린트

검지offer-면접문제 61: 지그재그 순서로 두 갈래 나무 프린트

Solution1:

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;
        if(pRoot == NULL)
            return res;
        vector<int> temp;
        int symbol = 1, cur = 1, next = 0;// symbol%2 == 1， ； 
        queue<struct TreeNode*> queue_tree;
        queue_tree.push(pRoot);
        while(!queue_tree.empty()) {
            temp.push_back(queue_tree.front()->val);
            cur--;
            if(queue_tree.front()->left != NULL) {
                queue_tree.push(queue_tree.front()->left);
                next++;
            }
            if(queue_tree.front()->right != NULL) {
                queue_tree.push(queue_tree.front()->right);
                next++;
            }
            if(cur == 0) {
                if(symbol%2 == 1) 
                    res.push_back(temp);
                else {
                    vec_swap(temp);
                    res.push_back(temp);
                }
                temp.clear();
                cur = next;
                next = 0;
                symbol++;
            }
            queue_tree.pop();
        }
        return res;
    }

    void vec_swap(vector<int> &temp) {
        int i = 0, j = temp.size() - 1, temp_val = 0;
        while(i < j) {
            temp_val = temp[i];
            temp[i] = temp[j];
            temp[j] = temp_val;
            i++;
            j--;
        }
        return;
    }

};

Solution2:

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;
        if(pRoot == NULL)
            return res;
        vector<int> temp;
        stack<struct TreeNode* > stack_node[2];// ， ， TreeNode*
        int cur = 0, next = 1;
        stack_node[cur].push(pRoot);
        while(!stack_node[0].empty() || !stack_node[1].empty()) {
            temp.push_back(stack_node[cur].top()->val);
            if(cur == 0) {
                if(stack_node[cur].top()->left != NULL)
                    stack_node[next].push(stack_node[cur].top()->left);
                if(stack_node[cur].top()->right != NULL)
                    stack_node[next].push(stack_node[cur].top()->right);
            }
            else {
                if(stack_node[cur].top()->right != NULL)
                    stack_node[next].push(stack_node[cur].top()->right);
                if(stack_node[cur].top()->left != NULL)
                    stack_node[next].push(stack_node[cur].top()->left);
            }
            stack_node[cur].pop();
            if(stack_node[cur].empty()) {
                res.push_back(temp);
                temp.clear();
                cur = 1 - cur;
                next = 1 - next;
            }
        }
        return res;
    }
};