Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

One, foreword

Brush problem!!

Start brushing “finger Offer” for 31 days. Finish time: 2022.3.6 ~ 2022.3.20.




Second, the subject

Topic:

  1. Prints the binary tree from top to bottom
  2. Print binary tree II from top to bottom
  3. Prints binary tree III from top to bottom

(1) Interview question 32-I. Print the binary tree from top to bottom

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], 3 / \ 9 20 / \ 15 7 Returns: [3,9,20,15,7]Copy the code

Warning: The total number of nodes <= 1000

Answer key

The typicalBFSTopic:

AC code is as follows:

class Solution {
    public int[] levelOrder(TreeNode root) {
        if (null == root) return new int[0];

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


Offer 32-II. Print binary tree II from top to bottom

Topic describes

The binary tree is printed from top to bottom layer, with nodes of the same layer printed from left to right, each layer printed to a row.

 

For example: for a given binary tree: [3,9,20, null, null, 15, 7], 3/20 / \ \ 9 15 7 returns to its level traversal results: [[3], [9], [15, 7]]Copy the code

Tip:

  • The total number of nodes <= 1000

Answer key

AC code is as follows:

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


(3) Finger Offer 32-III. Print binary tree III from top to bottom

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: for a given binary tree: [3,9,20, null, null, 15, 7], 3/20 / \ \ 9 15 7 returns to its level traversal results: [[3], [20, 9], [15, 7]]Copy the code

Warning: The total number of nodes <= 1000

Answer key

AC code is as follows:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (null == root) return Collections.emptyList();
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean isRight = true;
        while(! queue.isEmpty()) {int size = queue.size();
            List<Integer> tmp = new ArrayList<>(size);
            for (int i = 0; i < size; ++i) {
                TreeNode node = queue.poll();
                if (null! = node.left) queue.add(node.left);if (null! = node.right) queue.add(node.right); tmp.add(node.val); }if(result.size() % 2= =1) Collections.reverse(tmp);
            result.add(tmp);
        }
        returnresult; }}Copy the code