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

链接：103.二叉树的锯齿形层序遍历
难度：Medium
标签：树、广度优先搜索、二叉树
简介：给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

题解 1 - javascript

• 编辑时间：2020-04-26
• 执行用时：76ms
• 内存消耗：34.1MB
• 编程语言：javascript
• 解法介绍：判断高度为偶数时倒序

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function (root) {
  if (root === null) return [];
  const res = [];
  const queue = [root];
  let height = 1;
  const pushNode = () => {
    let valArr = [];
    for (const node of queue) valArr.push(node.val);
    if (height % 2 === 0) res.push(valArr.reverse());
    else res.push(valArr);
  };
  pushNode();
  let size = 1;
  while (queue.length !== 0) {
    const node = queue.shift();
    if (node.left !== null) queue.push(node.left);
    if (node.right !== null) queue.push(node.right);
    if (--size === 0) {
      height++;
      size = queue.length;
      if (queue.length !== 0) pushNode();
    }
  }
  return res;
};

题解 2 - c

• 编辑时间：2021-11-28
• 内存消耗：7.1MB
• 编程语言：c
• 解法介绍：修改层序遍历，偶数层倒序。

#define MAX 2000
int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int **arr = (int **)malloc(sizeof(int) * MAX);
    *returnSize = 0;
    *returnColumnSizes = (int *)malloc(sizeof(int) * MAX);
    if (!root) return arr;
    // 维护队列储存节点信息
    struct TreeNode *q[2000];
    q[0] = root;
    // 维护队列头尾指针
    int head = 0, tail = 1;
    // 维护当前层的元素数量，当前遍历的层级
    int size = 1, height = 1, order = -1;
    arr[0] = (int *)malloc(sizeof(int));
    arr[0][0] = root->val;
    (*returnColumnSizes)[0] = 1;
    while (head != tail) {
        // 每次出队一个节点
        struct TreeNode *node = q[head++];
        // 若左节点不为空则入队
        if (node->left) q[tail++] = node->left;
        // 若右节点不为空则入队
        if (node->right) q[tail++] = node->right;
        // 若当前层无元素，说明队列里都是下一层的元素
        if (--size == 0) {
            size = tail - head;
            *returnSize += 1;
            (*returnColumnSizes)[height] = size;
            arr[height] = (int *)malloc(sizeof(int) * size);
            if (order == 1) for(int i = head; i < tail; i++) arr[height][i - head] = q[i]->val;
            else for(int i = tail - 1; i >= head; i--) arr[height][tail - 1 - i] = q[i]->val;
            order *= -1;
            ++height;
        }
    }
    return arr;
}

题解 3 - python

• 编辑时间：2024-02-16
• 执行用时：40ms
• 内存消耗：16.66MB
• 编程语言：python
• 解法介绍：bfs。

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        q = deque() 
        q.append(root)
        size = 1
        ans = [[root.val]]
        while q:
            node = q.popleft()
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
            size -= 1
            if size == 0:
                size = len(q)
                if q: ans.append([node.val for node in q])
        for i in range(1, len(ans), 2):
            ans[i] = ans[i][::-1]
        return ans