[LeetCode 노트] Binary Tree Zigzag Level Order Traversal 두 갈래 트리 Z자형 훑어보기

생각:
사실은 이전 문제(이차 나무의 층층이 훑어보는 것)와 매우 비슷하다. 처음에 생각한 것은 대기열로 한 층의 노드를 저장하는 것이다. 이때 대기열의size를 계산하고 다음에size개부터 반대로 찾으려고 한다.어, 이거 먼저 들어가서 나오잖아, 스택으로!아니야, 매번 노드를 꺼낼 때마다 이 노드의 좌우 노드를 계속 저장해야 해. 그건 이 층이 다음 층을 다 찾지 못하고 창고를 눌러 들어온 게 아니야.위치에 따라 접근이 편리하려면 당연히 벡터를 사용해야 한다!두 번째 문제는 왼쪽에서 오른쪽으로 저장하는 것과 오른쪽에서 왼쪽으로 저장하는 것이 층마다 교차하기 때문에 판단이 하나 더 필요하다는 것이다(여기는 내가 짝짓기로 판단한다)
포인트: 1.queue를 사용하지 않고vector를 사용합니다.2. 왼쪽에서 오른쪽과 오른쪽에서 왼쪽은 짝짓기로 판단해야 한다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector> zigzagLevelOrder(TreeNode* root) {
        vector> v;
        TreeNode* p;
        vector q; // vector ， queue
        if (root==NULL)
            return v;
        else{
            q.push_back(root);
            int n = 2;
            while (!q.empty()){
                vector v2;
                int size = q.size();
                for (int i = size; i > 0; i--){
                    p = q[i-1];
                    v2.push_back(p->val);
                    q.erase(q.begin()+i-1);
                    if(n%2==0){
                        if(p->left!=NULL)
                            q.push_back(p->left);
                        if(p->right!=NULL)
                            q.push_back(p->right);
                    }
                    else{
                        if(p->right!=NULL)
                            q.push_back(p->right);
                        if(p->left!=NULL)
                            q.push_back(p->left);
                    }
                }
                v.push_back(v2);
                n = (n+1)%2;
            }
        }
        return v;
    }
};

반성: 처음에 문제를 풀었는데vector의 조작 함수에 대해 잘 몰라요. 연습을 많이 해야 돼요.