Subject to introduce

Force buckle 103: leetcode-cn.com/problems/bi…

Analysis of the

This problem is a variation of “102. Binary tree sequence traversal”, the final output requirements have changed, requiring us to determine the output order of each layer according to the odd and even number of layers. Specify that the root node of the binary tree is layer 00. If the current level is even, output the node value of the current level from left to right; otherwise, output the node value of the current level from right to left.

We can still use the idea of question 102 to modify the breadth-first search, traverse the tree layer by layer, and maintain all elements of the current layer with queues. When the queue is not empty, the length size of the current queue is obtained, and size elements are removed from the queue each time for expansion, and then the next iteration is carried out.

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.

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.

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        nodeQueue.offer(root);
        // Determine whether to reverse the display layer element
        boolean isOrderLeft = true;

        while(! nodeQueue.isEmpty()) { Deque<Integer> levelList =new LinkedList<Integer>();
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode curNode = nodeQueue.poll();
                if (isOrderLeft) {
                    // There is no need to reverse
                    levelList.offerLast(curNode.val);
                } else {
                    // Need to reverse
                    levelList.offerFirst(curNode.val);
                }
                if(curNode.left ! =null) {
                    nodeQueue.offer(curNode.left);
                }
                if(curNode.right ! =null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            // Alternately change whether to reverse the flagisOrderLeft = ! isOrderLeft; }returnans; }}Copy the code