[LeetCode Daily Question] - 103. Zigzag Level Order Traversal of Binary Tree

一【题目类别】

• 二叉树

二【题目难度】

• 中等

三【题目编号】

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

四【题目描述】

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

五【题目示例】

• 示例 1：
  
  输入：root = [3,9,20,null,null,15,7]
  输出：[[3],[20,9],[15,7]]

• 示例 2：
  输入：root = [1]
  输出：[[1]]

• 示例 3：
  输入：root = []
  输出：[]

六【题目提示】

• 树中节点数目在范围 [0, 2000] 内
• -100 <= Node.val <= 100

七【解题思路】

• The level-order traversal is definitely usedBFS（广度优先搜索）
• Based on this idea, level-order traversal is performed,It is relatively simple for layer-order traversal,Simply scan the elements of this layer, pop them from the queue and add them to the result array
• But the problem requires that the left and right order of storage is constantly reversed,So set a flag bit,Initially stored from left to right,Then after each layer is stored,修改标志位,Let it store right to left.By constantly modifying the flag bits, the layer sequence storage with different left and right orders is achieved

八【时间频度】

• 时间复杂度：$O(n)$,其中$n$为树的节点个数
• 空间复杂度：$O(n)$,其中$n$为树的节点个数

九【代码实现】

1. Java语言版

package Tree;

import java.util.*;

public class p103_ZigzagOrderTraversalOfBinaryTrees {
    

    int val;
    p103_ZigzagOrderTraversalOfBinaryTrees left;
    p103_ZigzagOrderTraversalOfBinaryTrees right;

    public p103_ZigzagOrderTraversalOfBinaryTrees() {
    
    }

    public p103_ZigzagOrderTraversalOfBinaryTrees(int val) {
    
        this.val = val;
    }

    public p103_ZigzagOrderTraversalOfBinaryTrees(int val, p103_ZigzagOrderTraversalOfBinaryTrees left, p103_ZigzagOrderTraversalOfBinaryTrees right) {
    
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static void main(String[] args) {
    
        p103_ZigzagOrderTraversalOfBinaryTrees root = new p103_ZigzagOrderTraversalOfBinaryTrees(3);
        p103_ZigzagOrderTraversalOfBinaryTrees left = new p103_ZigzagOrderTraversalOfBinaryTrees(9);
        p103_ZigzagOrderTraversalOfBinaryTrees right = new p103_ZigzagOrderTraversalOfBinaryTrees(20);
        p103_ZigzagOrderTraversalOfBinaryTrees right1 = new p103_ZigzagOrderTraversalOfBinaryTrees(15);
        p103_ZigzagOrderTraversalOfBinaryTrees right2 = new p103_ZigzagOrderTraversalOfBinaryTrees(7);
        root.left = left;
        root.right = right;
        right.left = right1;
        right.right = right2;
        List<List<Integer>> res = zigzagLevelOrder(root);
        System.out.println("res = " + res);
    }

    public static List<List<Integer>> zigzagLevelOrder(p103_ZigzagOrderTraversalOfBinaryTrees root) {
    
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        boolean flag = true;
        if (root == null) {
    
            return res;
        }
        Queue<p103_ZigzagOrderTraversalOfBinaryTrees> queue = new ArrayDeque<p103_ZigzagOrderTraversalOfBinaryTrees>();
        queue.offer(root);
        while (!queue.isEmpty()) {
    
            int size = queue.size();
            Deque<Integer> list = new LinkedList<Integer>();
            for (int i = 0; i < size; i++) {
    
                p103_ZigzagOrderTraversalOfBinaryTrees temp = queue.poll();
                if (flag) {
    
                    list.offerLast(temp.val);
                } else {
    
                    list.offerFirst(temp.val);
                }
                if (temp.left != null) {
    
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
    
                    queue.offer(temp.right);
                }
            }
            res.add(new LinkedList<Integer>(list));
            if (flag) {
    
                flag = false;
            } else {
    
                flag = true;
            }
        }
        return res;
    }

}

2. C语言版

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

struct TreeNode
{
    
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes)
{
    
	int** res = (int**)malloc(sizeof(int*) * 2001);
	*returnColumnSizes = (int*)malloc(sizeof(int) * 2001);
	*returnSize = 0;
	struct TreeNode* queue[2001];
	int front = 0;
	int rear = 0;
	bool flag = true;
	if (root == NULL)
	{
    
		(*returnColumnSizes)[*returnSize] = 0;
		return res;
	}
	queue[rear++] = root;
	while (front != rear)
	{
    
		res[*returnSize] = (int*)malloc(sizeof(int) * 2001);
		(*returnColumnSizes)[*returnSize] = 0;
		int size = (rear - front + 2001) % 2001;
		int count = 0;
		for (int i = 0; i < size; i++)
		{
    
			struct TreeNode* temp = queue[front++];
			if (flag)
			{
    
				res[*returnSize][count] = temp->val;
			}
			else
			{
    
				res[*returnSize][size - count - 1] = temp->val;
			}
			if (temp->left != NULL)
			{
    
				queue[rear++] = temp->left;
			}
			if (temp->right != NULL)
			{
    
				queue[rear++] = temp->right;
			}
			count++;
		}
		(*returnColumnSizes)[*returnSize] = count;
		*returnSize = *returnSize + 1;
		if (flag)
		{
    
			flag = false;
		}
		else
		{
    
			flag = true;
		}
	}
	return res;
}

/*主函数省略*/

十【提交结果】

1. Java语言版
   

2. C语言版