검지offer 면접문제.지그재그 순서로 두 갈래 나무를 인쇄하다

제목 설명

함수는 지그재그로 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로, 두 번째 줄은 오른쪽에서 왼쪽으로, 세 번째 줄은 왼쪽에서 오른쪽으로, 다른 줄은 이와 같이 인쇄합니다.
 
방법 1:
정상적인 차원을 두루 돌아다니며 일반 대열을 이용한다.홀수행(0부터 계산)을 만나면 이 층의 결과를 역순한다.

 1 class Solution {
 2 public:
 3     vectorint> > Print(TreeNode* pRoot) {
 4         if(pRoot==nullptr){return {};}
 5         queue my_queue;
 6         my_queue.push(pRoot);
 7         vectorint>>res;
 8         vector<int> vec;
 9         int cnt=0;
10         while(not my_queue.empty()){
11             vec.clear();
12             int cur_siz=my_queue.size();
13             for(int i=0;ii){
14                 auto cur=my_queue.front();
15                 my_queue.pop();
16                 vec.push_back(cur->val);
17                 if(cur->left){
18                     my_queue.push(cur->left);
19                 }
20                 if(cur->right){
21                     my_queue.push(cur->right);
22                 }
23             }
24             if(cnt&1){
25                 reverse(vec.begin(),vec.end());
26             }
27             res.push_back(vec);
28             ++cnt;
29         }
30         return res;
31     }
32 };

 
방법 2:
양쪽 대기열을 이용하여 대기열의 순서는 항상 정상적이지만 홀수 줄은 오른쪽에서 왼쪽으로 흐르고 팝 오른쪽은 아이push가 왼쪽으로 들어간다.짝수 줄은 왼쪽에서 오른쪽으로 흐르고, 팝 왼쪽은 아이push가 오른쪽으로 들어간다.

 1 class Solution {
 2 public:
 3     vectorint> > Print(TreeNode* pRoot) {
 4         if(pRoot==nullptr){return {};}
 5         deque my_queue;
 6         my_queue.push_back(pRoot);
 7         vectorint>>res;
 8         int cnt=0;
 9         while(not my_queue.empty()){
10             res.push_back({});
11             int cur_siz=my_queue.size();
12             decltype(pRoot) cur;
13             for(int i=0;ii){
14                 if(cnt&1){
15                     cur=my_queue.back();
16                     my_queue.pop_back();
17                     if(cur->right){
18                         my_queue.push_front(cur->right);
19                     }
20                     if(cur->left){
21                         my_queue.push_front(cur->left);
22                     }
23                 }
24                 else{
25                     cur=my_queue.front();
26                     my_queue.pop_front();
27                     if(cur->left){
28                         my_queue.push_back(cur->left);
29                     }
30                     if(cur->right){
31                         my_queue.push_back(cur->right);
32                     }
33                 }
34                 res.back().push_back(cur->val);
35             }
36             ++cnt;
37         }
38         return res;
39     }
40 };