JAVA Exercise 73-III. Printing Binary Tree from Top to Bottom III

Please implement a function to print the binary tree in zigzag order, that is, the first line is printed in order from left to right, the second layer is printed in order from right to left, the third line is printed in order from left to right, and the others are printed in order. And so on.

For example:
Given a binary tree: [3,9,20,null,null,15,7],
       3
      /  \
    9   20
   /  \
 15   7

Return its level traversal results:
[
  [3],
  [20,9],
  [15,7]
]

hint:

  • Total number of nodes <= 1000

analyze:

Method: BFS+identification

implementation andII. Print binary tree from top to bottom II.The same, the difference is that the order of the elements in each layer is reversed. You can define a flag to record the left and right, and after traversing one layer, assign the flag to the other direction. There are many ways to reverse traverse, such as inserting at the top of the List collection each time, inserting from the head of the double queue, etc. The first one I use here.

Time complexity: O(n)
Space complexity: O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //Judge empty tree
        if(root == null){
            return new ArrayList();
        }
        //define queue
        Deque<TreeNode> queue = new ArrayDeque<>();
        //Push to stack
        queue.offerLast(root);
        //Create a List collection to store the List collection of each layer
        List<List<Integer>> res = new ArrayList<>();
        //Mark left and right printing
        boolean flag = true;
        //Traverse
        while(!queue.isEmpty()){
            //Get the queue length
            int size = queue.size();
            //Define a List collection to store the node values ​​of this layer
            List<Integer> list = new ArrayList<>();
            //Traverse by level
            while(size-- > 0){
                //pop
                TreeNode node = queue.pollFirst();
                //Add node value
                //from left to right
                if(flag){
                    list.add(node.val);
                }
                //right to left
                else{
                    list.add(0, node.val);
                }
                //The left node is not empty and adds the left node
                if(node.left != null){
                    queue.offerLast(node.left);
                }
                //The right node is not empty and adds the right node
                if(node.right != null){
                    queue.offerLast(node.right);
                }
            }
            //Change the printing direction  
            flag = !flag;
            //Add the List collection to the List collection
            res.add(list);
        }
        return res;
    }
}

Question source: LeetCode
Link: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof

Related Posts

IDEA’s high-quality plug-in Translation has updated its translation engine following the IDEA 2022.3 version.

[SpringBoot Series] How SpringBoot integrates SSMP

Alibaba Yu Jun: DingTalk should take the path of low-code practice

Design and implementation of epidemic drug purchase and delivery system based on Java+SpringBoot+vue+element

Java project: train ticket reservation system (java+JDBC+JSP+Servlet+html+mysql)

The detailed process of SpringBoot integrating Alibaba Cloud SMS service (guaranteed that beginners can also implement it)

Mockito + JUnit unit test example

“New Semester, New FLAG” Breaking the Limit

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*