二叉树的按层打印与ZigZag打印

[编程题]二叉树的按层打印与ZigZag打印

热度指数：1548 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一颗二叉树，分别实现按层和 ZigZag 打印二叉树。

ZigZag遍历: 意思是第一层从左到右遍历，第二层从右到左遍历，依次类推。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

输出描述:

先输出按层打印，再输出按ZigZag打印。

示例1

输入

输出

Level 1 : 1
Level 2 : 2 3
Level 3 : 4 5 6
Level 4 : 7 8
Level 1 from left to right: 1
Level 2 from right to left: 3 2
Level 3 from left to right: 4 5 6
Level 4 from right to left: 8 7

备注:

算法知识视频讲解

Java

pein531

用队列进行层次遍历，ZigZag遍历时用层号来区分从左往右打印还是从右往左打印。这个题要想AC的话需要注意一下空格问题，ZigZag打印时冒号前面是没有空格的，正常打印时冒号左右都有空格。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Queue;
import java.util.LinkedList;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 构建二叉树
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        TreeNode root = new TreeNode(Integer.parseInt(params[1]));
        HashMap<Integer, TreeNode> map = new HashMap<>();
        map.put(root.val, root);
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            int val = Integer.parseInt(params[0]);
            int leftVal = Integer.parseInt(params[1]);
            int rightVal = Integer.parseInt(params[2]);
            TreeNode node = map.get(val);
            if(leftVal != 0) {
                node.left = new TreeNode(leftVal);
                map.put(leftVal, node.left);
            }
            if(rightVal != 0) {
                node.right = new TreeNode(rightVal);
                map.put(rightVal, node.right);
            }
        }
        // 层次遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 1;
        while(!queue.isEmpty()){
            int queueSize = queue.size();
            System.out.print("Level " + level + " : ");
            for(int i = 0; i < queueSize; i++){
                TreeNode node = queue.poll();
                System.out.print(node.val + " ");
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            System.out.println();
            level ++;
        }
        // ZigZag层次遍历
        queue.offer(root);
        level = 1;
        while(!queue.isEmpty()){
            int queueSize = queue.size();
            if(level % 2 == 1){
                System.out.print("Level " + level + " from left to right: ");
                for(int i = 0; i < queueSize; i++){
                    TreeNode node = queue.poll();
                    System.out.print(node.val + " ");
                    if(node.left != null) queue.offer(node.left);
                    if(node.right != null) queue.offer(node.right);
                }
            }else{
                System.out.print("Level " + level + " from right to left: ");
                String[] layer = new String[queueSize];
                for(int i = 0; i < queueSize; i++){
                    TreeNode node = queue.poll();
                    layer[i] = String.valueOf(node.val);
                    if(node.left != null) queue.offer(node.left);
                    if(node.right != null) queue.offer(node.right);
                }
                for(int i = queueSize - 1; i >= 0; i--) System.out.print(layer[i] + " ");
            }
            level ++;
            System.out.println();
        }
    }
}

发表于 2021-11-14 10:28:21 回复(0)

Java

CoachZ

好醉好醉，两次没通过竟然是因为和标准输出的空格对不上！！！

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void printByLevel(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int level = 1;
        Node last = root;
        Node nlast = null;
        System.out.print("Level " + level++ + " : ");
        while (!queue.isEmpty()) {
            root = queue.poll();
            System.out.print(root.value + " ");
            if (root.left != null) {
                queue.offer(root.left);
                nlast = root.left;
            }
            if (root.right != null) {
                queue.offer(root.right);
                nlast = root.right;
            }
            if (root == last && !queue.isEmpty()) {
                System.out.println();
                System.out.print("Level " + level++ +" : ");
                last = nlast;
            }
        }
    }

    public static void printZigZag(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int level = 1;
        Node last = root;
        Node nlast = null;
        boolean judge = false;
        ArrayList<Node> arrayList = new ArrayList<>();
        System.out.print("Level " + level++ + " from left to right : ");
        while (!queue.isEmpty()) {
            root = queue.poll();
            arrayList.add(root);
            if (root.left != null) {
                queue.offer(root.left);
                nlast = root.left;
            }
            if (root.right != null) {
                queue.offer(root.right);
                nlast = root.right;
            }
            if (root == last && !queue.isEmpty()) {
                if (judge) {
                    for (int i = arrayList.size() - 1; i >= 0; i--) {
                        System.out.print(arrayList.get(i).value + " ");
                    }
                } else {
                    for (int i = 0; i <= arrayList.size() - 1; i++) {
                        System.out.print(arrayList.get(i).value + " ");
                    }
                }
                arrayList.clear();
                judge = !judge;
                System.out.println();
                if (judge) {
                    System.out.print("Level " + level++ + " from right to left : ");
                } else {
                    System.out.print("Level " + level++ + " from left to right : ");
                }
                last = nlast;
            }
        }
        if (judge) {
            for (int i = arrayList.size() - 1; i >= 0; i--) {
                System.out.print(arrayList.get(i).value + " ");
            }
        } else {
            for (int i = 0; i <= arrayList.size() - 1; i++) {
                System.out.print(arrayList.get(i).value + " ");
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = br.readLine().split(" ");
        int n = Integer.parseInt(strings[0]);
        int root = Integer.parseInt(strings[1]);
        Node head1 = new Node(root);
        int[][] arr1 = new int[n + 1][2];
        for (int i = 0; i < n; i++) {
            strings = br.readLine().split(" ");
            arr1[Integer.parseInt(strings[0])][0] = Integer.parseInt(strings[1]);
            arr1[Integer.parseInt(strings[0])][1] = Integer.parseInt(strings[2]);
        }
        createTree(head1, arr1);
        printByLevel(head1);
        System.out.println();
        printZigZag(head1);
    }

    public static void createTree(Node head, int[][] arr) {
        if (head == null) {
            return;
        }
        if (arr[head.value][0] != 0) {
            head.left = new Node(arr[head.value][0]);
            createTree(head.left, arr);
        }
        if (arr[head.value][1] != 0) {
            head.right = new Node(arr[head.value][1]);
            createTree(head.right, arr);
        }
    }
}


class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int data) {
        this.value = data;
    }
}

发表于 2020-02-16 01:58:48 回复(0)