Make writing a habit together! This is the 15th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

The title

Serrated sequence traversal of binary trees

Given the root node of the binary tree, root, returns a zigzag sequence traversal of its node value. (that is, the next layer is traversed from left to right, then right to left, and so on, alternating between layers).

Example 1:

Input: root = [3,9,20, null, null, 15, 7] output: [[3], [20, 9], [15, 7]]Copy the code

Example 2:

Input: root = [1]Copy the code

Example 3:

Input: root = [] Output: []Copy the code

Tip:

The number of nodes in the tree is in the range [0, 2000] -100 <= node. val <= 100Copy the code

Answer key

Analysis of the problem solving

Their thinking

  1. This topic can adopt breadth-first search to traverse the tree layer by layer and maintain all elements of the current layer with the queue. When the queue is not empty, the length size of the current queue is obtained, and size elements are taken out from the queue for expansion each time, and then the next iteration is carried out.

  2. In order to satisfy the zigzagging pattern of “first left to right, then right to left”, we can use the data structure of “double-ended queue” to maintain the output order of node values of the current layer.

  3. A double-endian queue is a queue in which elements can be inserted at either end of the queue. We still expand from left to right as breadth-first searches traverse the current tier and expand the next tier, but for the current tier we maintain a variable isOrderLeft that records from left to right or from right to left:

    • From left to right, we insert each iterated element to the end of the two-ended queue.
    • If we go from right to left, we insert the traversed element each time to the head of the two-ended queue.

And when we’re done iterating we have an array of answers.

The complexity of the

Time complexity O(N) Space complexity O(N)

The problem solving code

The solution code is as follows (there are detailed notes in the code) :

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        // 1. Check whether it is empty
        if (root == null) {
            return ans;
        }

        // queue implements BFS layer traversal
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.offer(root);
        boolean isOrderLeft = true;

        while(! nodeQueue.isEmpty()) {// Define a double-ended queue to store the values of the current layer
            Deque<Integer> levelList = new LinkedList<Integer>();
            // Get the number of current layers
            int size = nodeQueue.size();
            // The queue is traversed by the value of this layer and out of the queue, according to the flag bit into the double-endian queue, and then according to the fixed sequential read next layer
            for (int i =0; i< size; i++) {
                // Get the node
                TreeNode curNode = nodeQueue.poll();
                if (isOrderLeft) {
                    / / order
                    levelList.offerLast(curNode.val);
                } else {
                    / / reverse
                    levelList.offerFirst(curNode.val);
                }

                // Get the value of the next layer node (from left to right)
                if(curNode.left ! =null) {
                    nodeQueue.offer(curNode.left);
                } 

                if(curNode.right ! =null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            // Flag bit conversionisOrderLeft = ! isOrderLeft; }returnans; }}Copy the code

Feedback results after submission (because the topic has not been optimized, the performance is mediocre) :

The reference information

  • Serrated sequence traversal for binary trees