[LeetCode] 103. Binary Tree Zigzag Level Order Traversal

轉自LeetCode

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]
]

<Solution>

這題一樣是要 level order traversal，但第一列是從左至右，然後第二列是要從右至左，但三列要從左至右，這樣的規則下去

一樣可以使用 Binary Tree Level Order Traversal 的方式去解

只是在偶數列的時候，要反轉一下答案，這樣就可以了

code 如下

如果不想用 reverse() 來完成，還有使用 list 的做法

用題目的例子來說明

round1:

list : [3], size = 1, don't reverse

=> 從 list 的後面拿 node，此時 list 為空

=> level order : 3

=> 先檢查當前 node 的 left child 是否為空，不為空就放到 list，注意是用 push_front，list : [9]

=> 再檢查 node 的 right child 是否為空，不為空放到 list，注意是用 push_front，list : [20, 9]

routd2:

list : [20, 9], size = 2, need reverse

=> 從 list 的前面拿 node，list = [9]

=> level order : 20

=> 先檢查 right child 是否為空，不為空放到 list，注意是用 push_back，list : [9, 7]

=> 先檢查 left child 是否為空，不為空放到 list，注意是用 push_back，list : [9, 7, 15]

=> 從 list 的前面拿 node，list = [7, 15]

=> level order : 20，9

=> 先檢查 right child 是否為空，不為空放到 list，注意是用 push_back，list : [7, 15]

=> 先檢查 left child 是否為空，不為空放到 list，注意是用 push_back，list : [7, 15]

round3:

list : [7, 15], size = 2, don't reverse

=> 從 list 的後面拿 node，list : [7]

=> level order : 15

=> 先檢查 left child 是否為空，不為空就放到 list，注意是用 push_front，list : [15]

=> 再檢查 right child 是否為空，不為空放到 list，注意是用 push_front，list : [15]

=> 從 list 的後面拿 node，list : []

=> level order : 15，7

=> 先檢查 left child 是否為空，不為空就放到 list，注意是用 push_front，list : []

=> 再檢查 right child 是否為空，不為空放到 list，注意是用 push_front，list : []

根據以上方式，需要多用一個 bool 來判斷是否要 reverse，然後做對應的操作方式即可

code 如下