首页 > 试题广场 >

二叉树的按层打印与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

输入

8 1
1 2 3
2 4 0
4 0 0
3 5 6
5 7 8
6 0 0
7 0 0
8 0 0

输出

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

备注:

用队列进行层次遍历,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)
我就是一傻子,写这么长代码,题目还是简单??
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int v[500001][2];

void Level(int root){
    queue<int>que;
    que.push(root);
    int level = 1;
    while(!que.empty()){
        int size = que.size();
        cout<<"Level " <<level<<" : ";
        for(int i = 0;i<size;++i){
            int top = que.front();
            que.pop();
            cout<<top<<" ";
            if(v[top][0]){
                que.push(v[top][0]);
            }
            if(v[top][1]){
                que.push(v[top][1]);
            }
        }
        ++level;
        cout<<endl;
    }// while
}

void ZigZag(int root){
    queue<int>q;
    q.push(root);
    int flag = 1;
    int level = 1;
    while(!q.empty()){
        if(flag == 1){
            cout<<"Level "<<level<<" from"<<" left"<<" to"<<" right: ";
        }else{
            cout<<"Level "<<level<<" from"<<" right"<<" to"<<" left: ";
        }
        vector<int>temp;
        int size = q.size();
        for(int i = 0;i<size;++i){
            int top = q.front();
            q.pop();
            temp.push_back(top);
            if(v[top][0]){
                q.push(v[top][0]);
            }
            if(v[top][1]){
                q.push(v[top][1]);
            }
        }
        if(flag == 1){
            for(int i = 0;i<temp.size();++i){
                cout<<temp[i]<<" ";
            }
            cout<<endl;
        }else{
            for(int i = temp.size()-1;i>=0;--i){
                cout<<temp[i]<<" ";
            }
            cout<<endl;
        }
        ++level;
        flag *=  -1;
    }
}
int main(){
    int n,root;
    cin>>n>>root;
    for(int i = 0;i<n;++i){
        int p;
        cin>>p;
        cin>>v[p][0];
        cin>>v[p][1];
    }
    Level(root);
    ZigZag(root);
    return 0;
}


发表于 2020-07-07 17:36:17 回复(0)
#include <stdio.h>
#include <stdlib.h>

#define not !

typedef int Id;
const int N = 5E5;

typedef struct {
  Id id;
  Id l_child, r_child;
} TreeNodeInfo, *INFO;

typedef struct TreeNode {
  Id id;
  struct TreeNode* left;
  struct TreeNode* right;
} TreeNode, *PTNode, *BT;

void swap(int* a, int* b) {
  if (a == b) return;
  *a ^= *b, *b ^= *a, *a ^= *b;
}

void reverse(int* arr, const int arrSize) {
  int l = 0, r = arrSize - 1;
  while (l < r) swap(arr + l++, arr + r--);
}


BT CreateBT(INFO infos, Id root_id) {
  // recursion exit condition
  if (!root_id) return NULL;
  
  BT t = (PTNode) malloc(sizeof(TreeNode));
  if (!t) return NULL;
  
  t->id    = root_id;
  t->left  = CreateBT(infos, (*(infos + root_id)).l_child);
  t->right = CreateBT(infos, (*(infos + root_id)).r_child);
  return t;
}

void levelOrder(BT t) {
  // corner case
  if (!t) return;
  
  PTNode q[N];
  int front = 0, rear = 0;
  *(q + rear++) = t;
  
  int level = 1;
  while (front < rear) {
    fprintf(stdout, "Level %d :", level);
    size_t s = rear - front;
    while (s--) {
      t = *(q + front++);
      fprintf(stdout, " %d", t->id);
      if (t->left)  *(q + rear++) = t->left;
      if (t->right) *(q + rear++) = t->right;
    }
    ++level;
    fputc(10, stdout);
  }
}

void levelOrderZigZag(BT t) {
  // corner case
  if (!t) return;
  
  PTNode q[N];
  int front = 0, rear = 0;
  *(q + rear++) = t;
  
  int level = 1;
  int i, vals[(int)1E4], valsSize;
  while (front < rear) {
    printf(level & 1 ? "Level %d from left to right:"
            : "Level %d from right to left:", level);
    
    valsSize = 0;
    size_t s = rear - front;
    while (s--) {
      t = *(q + front++);
      *(vals + valsSize++) = t->id;
      if (t->left)  *(q + rear++) = t->left;
      if (t->right) *(q + rear++) = t->right;
    }
    if (!(level & 1)) reverse(vals, valsSize);
    for (i = 0; i < valsSize; ++i)
      fprintf(stdout, " %d", *(vals + i));
    ++level;
    fputc(10, stdout);
  }
}

int main(const int argc, const char* const argv[]) {
  int n, root_id;
  fscanf(stdin, "%d %d", &n, &root_id);
  
  TreeNodeInfo infos[n + 1];
  Id fa, lch, rch;
  while (n--) {
    fscanf(stdin, "%d %d %d", &fa, &lch, &rch);
    (*(infos + fa)).id = fa;
    (*(infos + fa)).l_child = lch;
    (*(infos + fa)).r_child = rch;
  }
  
  BT t = CreateBT(infos, root_id);
  levelOrder(t);
  levelOrderZigZag(t);
  return 0;
}

发表于 2021-08-03 17:33:55 回复(0)
import java.util.*;

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

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node head = constructTree(sc, n);
        printLevels(head);
        printZigzag(head);
    }
     
    public static Node constructTree (Scanner sc, int n) {
        HashMap<Integer, Node> map = new HashMap<>();
        int rootVal = sc.nextInt();
        Node root = new Node(rootVal);
        map.put(rootVal, root);
        for (int i = 0; i < n; i++) {
            int nodeVal = sc.nextInt();
            int leftVal = sc.nextInt();
            int rightVal = sc.nextInt();
            if (map.containsKey(nodeVal)) {
                Node tmpNode = map.get(nodeVal);
                Node leftNode = leftVal == 0 ? null : new Node(leftVal);
                Node rightNode = rightVal == 0 ? null : new Node(rightVal);
                tmpNode.left = leftNode;
                tmpNode.right = rightNode;
                if (leftVal != 0)
                    map.put(leftVal, leftNode);
                if (rightVal != 0)
                    map.put(rightVal, rightNode);
            }
        }
        return root;
    }
    
    //问题在于何时换行,只需知道何时到了一个level的结尾即可,用两个变量last与nlast记录
    //本行结尾与下一行结尾,每次让last = nlast。而nlast则一直跟踪记录宽度优先的队列中
    //新加入的数即可。
    public static void printLevels(Node head) {
        if (head == null) {
            return;
        }
        Node last = head;
        Node nlast = null;
        Queue<Node> q = new LinkedList<Node>();
        q.offer(head);
        int level = 1;
        System.out.print("Level " + (level++) + " : ");
        while (!q.isEmpty()) {
            Node cur = q.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                q.offer(cur.left);
                nlast = cur.left;
            }
            if (cur.right != null) {
                q.offer(cur.right);
                nlast = cur.right;
            }
            if (cur == last && !q.isEmpty()) {
                System.out.println();
                System.out.print("Level " + (level++) + " : ");
                last = nlast;
            }
        }
        System.out.println();
    }
    
    public static void printZigzag (Node head) {
        if (head == null)
            return;
        Node cur = head;
        Node last = head;
        Node nlast = null;
        Deque<Node> dq = new LinkedList<Node>();
        dq.offerFirst(cur);
        int level = 1;
        boolean fLtR = true;
        System.out.print("Level " + (level++) + " from left to right: " );
        while (!dq.isEmpty()) {
            if (fLtR) {
                head = dq.pollFirst();
                if (head.left != null) {
                    dq.offerLast(head.left);
                    nlast = nlast == null ? head.left : nlast;
                }
                if (head.right != null) {
                    dq.offerLast(head.right);
                    nlast = nlast == null ? head.right : nlast;
                }
            }
            else {
                head = dq.pollLast();
                if (head.right != null) {
                    dq.offerFirst(head.right);
                    nlast = nlast == null ? head.right : nlast;
                }
                if (head.left != null) {
                    dq.offerFirst(head.left);
                    nlast = nlast == null ? head.left : nlast;
                }
            }
            System.out.print(head.val + " ");
            if (last == head && !dq.isEmpty()) {
                System.out.println();
                fLtR = !fLtR;
                if (fLtR)
                    System.out.print("Level " + (level++) + " from left to right: " );
                else
                    System.out.print("Level " + (level++) + " from right to left: " );
                last = nlast;
                nlast = null;
            }
        }
        System.out.println();
    }
}

发表于 2021-06-14 21:29:24 回复(0)
输入根本就不是先序
6 0 0
7 0 0
8 0 0
不应先
7 0 0
8 0 0
再
6 0 0
还有输出:的位置呀!!!
编辑于 2021-05-18 09:47:39 回复(0)
class TreeNode:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None

def PrintFromTopToBottom(root):
    # write code here
    if not root:
        return []
    queue = [root]
    res = []
    while len(queue)>0:
        # 当前队列的大小为每层节点的个数
        level_size = len(queue)
        temp = []
        for _ in range(level_size):
            top = queue.pop(0)
            temp.append(top.val)
            if top.left:
                queue.append(top.left)
            if top.right:
                queue.append(top.right)
        res.append(temp)
    return res

def PrintZigZag(root):
    if not root:
        return []
    queue = [root]
    count = 0  # 标志位,判断当前是奇数还是偶数层
    res = []
    while len(queue):
        # 当前队列的大小为每层节点的个数
        level_size = len(queue)
        count += 1
        stack = []
        temp = []
        for _ in range(level_size):

            if count % 2 != 0:
                d = queue.pop(0)

                temp.append(d.val)

                if d.left:
                        queue.append(d.left)
                if d.right:
                        queue.append(d.right)
            else: # 对偶数层进行处理
                d = queue.pop()

                temp.append(d.val)
                stack.append(d)

                if len(stack) == level_size:
                    for _ in range(level_size):
                        q = stack.pop()
                        if q.left:
                            queue.append(q.left)
                        if q.right:
                            queue.append(q.right)
        res.append(temp)
    return res

if __name__ == "__main__":
    # a是二叉树节点个数,b是二叉树的根节点值
    n, r = map(int, input().split())
    root = TreeNode(r)
    nodes = {r: root}
    for _ in range(n):
        v, l, r = map(int, input().split())
        if l!= 0:
            nodes[l] = TreeNode(l)
            nodes[v].left = nodes[l]
        if r != 0:
            nodes[r] = TreeNode(r)
            nodes[v].right = nodes[r]
    # 按层打印
    res1 = PrintFromTopToBottom(root)
    #按ZigZag打印
    res2 = PrintZigZag(root)
    for i,r in enumerate(res1):
         print("Level {} : {}".format(i+1," ".join(str(x) for x in res1[i])))
    for i,r in enumerate(res2):
        if i%2==0:
            print("Level {} from left to right: {}".format(i+1, " ".join(str(x) for x in res2[i])))
        else:
            print("Level {} from right to left: {}".format(i+1, " ".join(str(x) for x in res2[i])))
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。75%通过。该怎么改进?
发表于 2020-07-18 16:10:52 回复(0)
这道题最难的地方是输出的格式,尤其是空格😂
发表于 2020-03-26 10:41:58 回复(0)
好醉好醉,两次没通过竟然是因为和标准输出的空格对不上!!!

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)
#include<bits/stdc++.h>
using namespace std;
void printByLevel(int root,int* lc,int* rc)
{
    if(!root) return;
    deque<int>q;
    q.push_back(root);
    int level = 1;
    while(!q.empty())
    {
        int len = q.size();
        cout<<"Level "<<level<<" :";
        for(int i=0;i<len;++i)
        {
            int cur = q.front();
            q.pop_front();
            cout<<" "<<cur;
            if(lc[cur]) q.push_back(lc[cur]);
            if(rc[cur]) q.push_back(rc[cur]);
        }
        cout<<endl;
        ++level;
    }
}
void printByZigZag(int root,int* lc,int* rc)
{
    if(!root) return;
    deque<int>q;
    int level = 1;
    q.push_back(root);
    while(!q.empty())
    {
        if(level&1)
        {
            cout<<"Level "<<level<<" from left to right:";
            int len = q.size();
            for(int i=0;i<len;++i)
            {
                int cur = q.front();
                q.pop_front();
                cout<<" "<<cur;
                if(lc[cur]) q.push_back(lc[cur]);
                if(rc[cur]) q.push_back(rc[cur]);
            }

        }
        else{
            cout<<"Level "<<level<<" from right to left:";
            int len = q.size();
            for(int i=0;i<len;++i)
            {
                int cur = q.back();
                q.pop_back();
                cout<<" "<<cur;
                if(rc[cur]) q.push_front(rc[cur]);
                if(lc[cur]) q.push_front(lc[cur]);
            }
        }
        cout<<endl;
        ++level;
    }

}
int main()
{
    int n,root;
    cin>>n>>root;
    int p;
    int* lc = new int[n+1];
    int* rc = new int[n+1];
    for(int i=0;i<n;++i)
    {
        cin>>p;
        cin>>lc[p]>>rc[p];
    }
    printByLevel(root,lc,rc);
    printByZigZag(root,lc,rc);
    return 0;
}
发表于 2020-02-05 15:26:11 回复(0)