103. 二叉树的锯齿形层序遍历

二叉树的锯齿形层序遍历

• 难度: medium
• 原始链接: https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal
• 标签: 广度优先遍历, 深度优先遍历

解法一: 广度优先遍历

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
  ans := [][]int{}
  if root == nil {
    return ans
  }
  queue := []*TreeNode{root}
  depth := 0
  for len(queue) > 0 {
    ans = append(ans, []int{})
    size := len(queue)
    for i := 0; i < size; i++ {
      if queue[i].Left != nil {
        queue = append(queue, queue[i].Left)
      }
      if queue[i].Right != nil {
        queue = append(queue, queue[i].Right)
      }
      if (depth & 1) == 0 {
        ans[depth] = append(ans[depth], queue[i].Val)
      } else {
        ans[depth] = append(ans[depth], queue[size-i-1].Val)
      }
    }
    queue = queue[size:]
    depth++
  }
  return ans
}

解法二: 深度优先遍历

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
  ans := [][]int{}
  var dfs func(node *TreeNode, depth int)
  dfs = func(node *TreeNode, depth int) {
    if node == nil {
      return
    }
    if len(ans) <= depth {
      ans = append(ans, []int{})
    }
    if (depth & 1) == 0 {
      ans[depth] = append(ans[depth], node.Val)
    } else {
      // 往切片的头部插入一个元素
      ans[depth] = append(ans[depth], -1)
      copy(ans[depth][1:], ans[depth])
      ans[depth][0] = node.Val
    }
    dfs(node.Left, depth+1)
    dfs(node.Right, depth+1)
  }
  dfs(root, 0)
  return ans
}