[LeetCode] Binary Tree Zigzag Level Order Traversal

문제

Given 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,null,null,15,7],

3 / \ 9 20 / \ 15 7

return its zigzag level order traversal as:

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

 

Approach

Level Order Traversal인데 기존과 다른 점은 지그재그인것

기존 구현과 비슷한데 차이점은

왼쪽으로 읽을 때는 vector의 뒤에서 부터 넣어주고

오른쪽으로 읽을 때는 vector의 앞에서 부터 넣어준다.

queue에 넣을때는 동일하게 왼쪽 오른쪽 순서로 넣어야하는데

괜히 오른쪽으로 읽을때는 오른쪽 왼쪽 순서로 넣었다가 해맸음

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_BinaryTreeZigzagLevelOrderTraversal.cpp