103. Binary Tree Zigzag Level Order Traversal

Medium
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1:
​
​
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
Constraints:
  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100

解題

解法一:將每層的節點值由左到右記錄起來,再將 level 是奇數的反轉
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
res := make([][]int, 0)
var bfs func(*TreeNode, int)
bfs = func(n *TreeNode, level int) {
if n == nil { return }
​
if len(res) == level {
res = append(res, []int{})
}
​
res[level] = append(res[level], n.Val)
bfs(n.Left, level + 1)
bfs(n.Right, level + 1)
}
​
bfs(root, 0)
​
for i:=1; i<len(res); i+=2 {
res[i] = ReverseSlice(res[i])
}
​
return res
}
​
func ReverseSlice(s []int) []int {
var r []int
for i := len(s) - 1; i >= 0; i-- {
r = append(r, s[i])
}
return r
}
解法二:使用兩個 stack
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
res := make([][]int, 0)
if root == nil { return res }
stack1 := make([]*TreeNode, 0)
stack2 := make([]*TreeNode, 0)
​
stack1 = append(stack1, root)
​
isEven := true
for len(stack1) > 0 || len(stack2) > 0 {
temp:=[]int{}
​
if isEven {
for len(stack1) != 0 {
node :=stack1[len(stack1)-1]
stack1 = stack1[:len(stack1)-1]
temp = append(temp, node.Val)
​
if node.Left != nil {
stack2 = append(stack2, node.Left)
}
if node.Right != nil {
stack2 = append(stack2, node.Right)
}
}
} else {
for len(stack2) != 0 {
node :=stack2[len(stack2)-1]
stack2 = stack2[:len(stack2)-1]
temp = append(temp, node.Val)
​
if node.Right != nil {
stack1 = append(stack1, node.Right)
}
if node.Left != nil {
stack1 = append(stack1, node.Left)
}
}
}
​
isEven = !isEven
​
if len(temp) > 0 {
res = append(res, temp)
}
}
​
return res
}
​