Pengjielee's blog

题目

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

给定二叉树 [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层序遍历如下：
[
  [3],
  [20,9],
  [15,7]
]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function (root) {
  // write code here
  const result = [];

  if (root === null) {
    return result;
  }

  const q = [];
  q.push(root);

  // 声明标识位
  let rev = true;

  while (q.length > 0) {
    const level = [];
    const len = q.length;
    for (let i = 0; i < len; i++) {
      const node = q.shift();
      if (rev) {
        level.push(node.val); //在数组末尾添加值
      } else {
        level.unshift(node.val); //在数组开头添加值
      }
      if (node.left != null) {
        q.push(node.left);
      }
      if (node.right != null) {
        q.push(node.right);
      }
    }
    result.push(level);
    // 标识位取反
    rev = !rev;
  }
  return result;
};

Go实现

package main

import (
  "fmt"
)

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func main() {
  root := &TreeNode{
    Val:   1,
    Left:  &TreeNode{Val: 2},
    Right: &TreeNode{Val: 3},
  }

  fmt.Println(zigzagLevelOrder(root))
}

func zigzagLevelOrder(root *TreeNode) (ans [][]int) {
  if root == nil {
    return
  }
  queue := []*TreeNode{root}
  for level := 0; len(queue) > 0; level++ {
    vals := []int{}
    q := queue
    queue = nil
    //遍历队列q生成下一层的节点队列，并且将当前队列的值加入val数组准备输出
    for _, node := range q {
      vals = append(vals, node.Val)
      if node.Left != nil {
        queue = append(queue, node.Left)
      }
      if node.Right != nil {
        queue = append(queue, node.Right)
      }
    }
    // 本质上和层序遍历一样，我们只需要把奇数层的元素翻转即可
    if level%2 == 1 {
      for i, n := 0, len(vals); i < n/2; i++ {
        vals[i], vals[n-1-i] = vals[n-1-i], vals[i]
      }
    }
    ans = append(ans, vals)
  }
  return
}