[OJ.leetcode] binary-tree-zigzag-level-order-traversal

https://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

iven a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

/* BFS를 응용해서, 자료구조를 queue 대신에 deque 또는 vector를 이용, 한번은 front에서부터, 한번은 back 에서부터 pop 하면 될 듯 Time complexity : O(n) 순회순서는 root(->) 1 level depth(<-) 2 level depth(->) ... 이므로 flag 변수를 하나주어 BFS 순회시에 순회 순서를 switch 하도록 구현하면 될 듯 핵심 : 어떻게 deque 내에서 level을 구분할 것인지 -> deque에 저장할떄 deque<deque<TreeNode*>> 형태로 저장해서 매 loop 순회마다 deque에있는 모든 element 들을 꺼내는 식으로 접근하면 쉽게 해결. 목표 : 단 한번에 accepted 결과 : 2번 실패 후 accpeted (순회할때, 자식 저장 순서도 고려했었어야 했는데(순회 방향에따라 번갈아 저장되므로) 이 부분 놓침) */ /** * 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; queue<deque<TreeNode*>> data; deque<TreeNode*> temp; bool toLeft = true; //start with left to right direction if(root == NULL) return res; temp.push_back(root); data.push(temp); temp.clear(); while(!data.empty()) { vector<int> innerContainer; deque<TreeNode*> container; temp = data.front(); //deque data.pop(); while(!temp.empty()) { if(toLeft) { if(temp.back()->left != NULL) { container.push_back(temp.back()->left); } if(temp.back()->right != NULL) { container.push_back(temp.back()->right); } } else { if(temp.back()->right != NULL) { container.push_back(temp.back()->right); } if(temp.back()->left != NULL) { container.push_back(temp.back()->left); } } innerContainer.push_back(temp.back()->val); temp.pop_back(); } res.push_back(innerContainer); if(toLeft) { toLeft = false; } else { toLeft = true; } if(!container.empty()) { data.push(container); container.clear(); } } return res; } };