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
}