This is the 25th day of my participation in Gwen Challenge

Print binary trees from top to bottom (sword at Offer32-1)

Topic describes

Each node of the binary tree is printed from top to bottom, and nodes of the same level are printed from left to right.

For example, given a binary tree: [3,9,20,null,null,15,7]

Example 1:

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns:

,9,20,15,7 [3]Copy the code

prompt

  • The total number of nodes <= 1000

Thought analysis

Print binary tree from top to bottom, we can go through a queue traversal, the start will be the first layer of the nodes in the queue, and then traverse the nodes in the queue, you can get the second layer of all nodes, and put these nodes in the queue, then iterate through this layer of nodes, we can get the third layer of all nodes, And then we iterate over all the nodes in the queue, and we can print the fourth layer of nodes, and we iterate over and over, and we get all the nodes. Finally, we iterate over these nodes, put them in an array, and return.

The code shown

Solution a:

public int[] levelOrder(TreeNode root) {
        if(root == null) {return new int[0];
        }
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(! queue.isEmpty()){ TreeNode node = queue.poll(); result.add(node.val);if(node.left ! =null){
                queue.add(node.left);
            }
            if(node.right ! =null){ queue.add(node.right); }}int[] arr = new int[result.size()];
        for(int i = 0; i < result.size(); i++){ arr[i] = result.get(i); }return arr;
    }
Copy the code

Print binary trees from top to bottom (sword at Offer32-3)

Topic describes

Implement a function to print a binary tree in glyph order, that is, the first line is printed from left to right, the second line is printed from right to left, the third line is printed from left to right, and so on.

For example, given a binary tree: [3,9,20,null,null,15,7],

Example 1:

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns the result of its hierarchical traversal:

[[3], [20,9], [15,7]Copy the code

prompt

  • The total number of nodes <= 1000

Thought analysis

This problem is similar to the above problem, just need to return is a two-dimensional array, print binary tree from top to bottom, we can go through a queue traversal, the start will be the first layer of the nodes in the queue, then traverse the nodes in the queue, and be able to get the second layer of all nodes, and put these nodes in the queue, And then we iterate through this layer of nodes, and we get all the nodes in the third layer, and then we iterate through all the nodes in the queue, and we print the nodes in the fourth layer, and we iterate over and over, and we get all the nodes. Finally, we iterate over these nodes, put them in an array, and return.

At the same time, we print the nodes of each layer in zigzag. At this time, we need to do the processing of each traversal node, obtain the size of the traversal queue in advance, and then enlarge an item of the two-dimensional array. Zigzag printing is judged by using odd and even numbers.

The code shown

Solution a:

public List<List<Integer>> levelOrder(TreeNode root) {
        
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) {return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int deep = 1;
        while(! queue.isEmpty()){int size = queue.size();
            List<Integer> innerList = new ArrayList<>();
            if(deep % 2! =0) {for(int i = 0; i < size; i++){ TreeNode node = queue.poll(); innerList.add(node.val);if(node.left ! =null){
                        queue.add(node.left);
                    }
                    if(node.right ! =null){ queue.add(node.right); }}}else {
                for(int i = 0; i < size; i++){ TreeNode node = queue.poll(); innerList.add(0,node.val);
                    if(node.left ! =null){
                        queue.add(node.left);
                    }
                    if(node.right ! =null){
                        queue.add(node.right);
                    }
                }
            }
            deep++;
            result.add(innerList);
        }
        return result;

    }
Copy the code

conclusion

Printing from top to bottom is called sequential traversal, and we should also master binary tree traversal.