ZigZagging on a Tree二叉树蛇形层次遍历(Java语言)

简介: ZigZagging on a Tree二叉树蛇形层次遍历(Java语言)

题目描述:

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” – that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

4726b256e87946f188365e2f21fc5300.png


Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.


Output Specification:

For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.


Sample Input:

8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1

Sample Output:

1 11 5 8 17 12 20 15

解题思路:

根据中序和后序创建二叉树,最后蛇形层次遍历(遍历一层就开始反转一次,Java中使用了LinkedList进行存储处理)

代码中有根据中序和后序创建二叉树的模板,有层次遍历的模板;

先序和中序创建二叉树的模板参考先序和中序创建二叉树

代码:

package text_9_25;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class ZigZaggingOnATree {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int in[] = new int[n];
    int post[] = new int[n];
    for(int i=0;i<n;i++)
      in[i] = scanner.nextInt();
    for(int i=0;i<n;i++)
      post[i] = scanner.nextInt();
    //创建二叉树
    Node root = BuildTree(in, 0, n-1, post, 0, n-1);
    
    //蛇形层次遍历
    PrintLevelOrder(root);

    
  }
  
  public static Node BuildTree(int in[],int ibegin,int iend,int post[],int pbegin,int pend) {
    if(ibegin>iend||pbegin>pend) return null;
    Node root = new Node(post[pend]);
    for(int i=ibegin;i<=iend;i++) {
      if(post[pend]==in[i]) {
        root.left = BuildTree(in, ibegin, i-1, post, pbegin, pbegin-ibegin+i-1);
        root.right = BuildTree(in, i+1, iend, post, pbegin-ibegin+i, pend-1);
      }
    }
    return root;
  }
  public static void PrintLevelOrder(Node root) {
    boolean reversed = false;//反转标志
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    int flag=1;//用于输出格式控制
    while(!queue.isEmpty()) {
      int size = queue.size();//当前层的节点数
      LinkedList<Integer> link = new LinkedList<>();//保存当前层结果,LinkedList可以前后插入
      for(int i=0;i<size;i++) {  //对应每一层
        Node temp = queue.poll();
        if(reversed) link.add(temp.data);
        else link.addFirst(temp.data);
        
        if(temp.left!=null) queue.add(temp.left);
        if(temp.right!=null) queue.add(temp.right);
      }
//      System.out.println(size);
      for(int j=0;j<link.size();j++) {
        if(flag==1) {
          System.out.print(link.get(j));
          flag=0;
        }
        else System.out.print(" "+link.get(j));
      }
      reversed =!reversed;  //每次反转
    }
  }

}
class Node{   //树节点类
  public int data;
  public Node left;
  public Node right;
  public Node(int data){
    this.data = data;
    left = right = null;
  }
}

目录
相关文章
|
3月前
|
JSON JavaScript 前端开发
Python+JAVA+PHP语言,苏宁商品详情API
调用苏宁商品详情API,可通过HTTP/HTTPS发送请求并解析响应数据,支持多种编程语言,如JavaScript、Java、PHP、C#、Ruby等。核心步骤包括构造请求URL、发送GET/POST请求及解析JSON/XML响应。不同语言示例展示了如何获取商品名称与价格等信息,实际使用时请参考苏宁开放平台最新文档以确保兼容性。
|
3月前
|
监控 Java API
Java语言按文件创建日期排序及获取最新文件的技术
这段代码实现了文件创建时间的读取、文件列表的获取与排序以及获取最新文件的需求。它具备良好的效率和可读性,对于绝大多数处理文件属性相关的需求来说足够健壮。在实际应用中,根据具体情况,可能还需要进一步处理如访问权限不足、文件系统不支持某些属性等边界情况。
221 14
|
4月前
|
Java 编译器 应用服务中间件
为什么说 Java 语言编译与解释并存的原因
在编程语言的世界里,Java以其独特的“编译与解释并存”特性独树一帜。这一特性不仅赋予了Java强大的跨平台能力,还使其在性能和灵活性上达到了很好的平衡。接下来,我们将深入探讨Java语言这一特性的本质、原理以及在实际应用中的体现。
112 6
|
4月前
|
分布式计算 Java 大数据
Java 语言基础概念与常识之主要特点解析
Java是一种广泛应用于企业级开发、移动应用(如Android)、大数据处理及云计算等领域的编程语言。其核心特点包括跨平台性(一次编写,到处运行)、面向对象设计、自动垃圾回收、多线程支持和高性能表现。Java通过JVM实现跨平台,具备强大的健壮性和安全性,同时拥有丰富的标准库与活跃的开发者社区。本文深入解析Java的技术优势及其在电商系统、大数据处理和云计算中的实际应用,并提供相关面试资料供学习参考。
134 0
|
4月前
|
网络协议 安全 Java
实现Java语言的文件断点续传功能的技术方案。
像这样,我们就完成了一项看似高科技、实则亲民的小工程。这样的技术实现不仅具备实用性,也能在面对网络不稳定的挑战时,稳稳地、不失乐趣地完成工作。
269 0
|
6月前
|
人工智能 安全 Java
智慧工地源码,Java语言开发,微服务架构,支持分布式和集群部署,多端覆盖
智慧工地是“互联网+建筑工地”的创新模式,基于物联网、移动互联网、BIM、大数据、人工智能等技术,实现对施工现场人员、设备、材料、安全等环节的智能化管理。其解决方案涵盖数据大屏、移动APP和PC管理端,采用高性能Java微服务架构,支持分布式与集群部署,结合Redis、消息队列等技术确保系统稳定高效。通过大数据驱动决策、物联网实时监测预警及AI智能视频监控,消除数据孤岛,提升项目可控性与安全性。智慧工地提供专家级远程管理服务,助力施工质量和安全管理升级,同时依托可扩展平台、多端应用和丰富设备接口,满足多样化需求,推动建筑行业数字化转型。
232 5
|
7月前
|
存储 Java 数据安全/隐私保护
Java语言位运算符详解
Java语言提供了7种位运算符:按位与(&)、按位或(|)、按位异或(^)、取反(~)、左移(&lt;&lt;)、带符号右移(&gt;&gt;)和无符号右移(&gt;&gt;&gt;)。这些运算符主要用于对long、int、short、byte和char类型的数据进行二进制位级别的操作,不能用于double、float和boolean类型。文中详细讲解了每种运算符的规则和应用场景,并指出位运算在实际开发中有重要应用价值,不仅限于面试。
308 2
|
Java
java实现简单的二叉树ADT
java实现简单的二叉树ADT
208 0
|
Java 程序员
java实现简单二叉树
java实现简单二叉树
430 0
java实现简单二叉树
用Java实现一个简单二叉树
前置知识: 什么是二叉树:一个递归的树形数据结构,每个节点最多有两个子节点;二叉树一般都是二分查找树,每个节点的值大于它左子节点的值,小于它右子节点的值
888 0
用Java实现一个简单二叉树