Tree Traversals Again(Java语言)(先序和中序创建二叉树)(遍历树)

简介: Tree Traversals Again(Java语言)(先序和中序创建二叉树)(遍历树)

题目描述:

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.


f8533843d15949c3972ab8f5cd5d5ab6.png

Figure 1

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.

Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.


Sample Input:

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:

3 4 2 6 5 1

解题思路:

通过题目可以发现push是先序遍历,pop是中序遍历,然后根据先序和中序构造树,后序遍历出结果。

代码:

package text2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class TreeTraversalsAgain {
  static ArrayList<Integer> post = new ArrayList<>();
  public static void main(String[] args) throws NumberFormatException, IOException {
    // TODO Auto-generated method stub
    BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    int n=Integer.parseInt(read.readLine());
    int pre[] = new int[n];
    int in[] = new int[n];
    
    Stack<Integer> stack = new Stack<>();
    for(int i=0,j=0,k=0;i<2*n;i++) {
      String[] str = read.readLine().split(" ");
      if(str[0].equals("Push")) {//前序
        pre[j]=Integer.parseInt(str[1]);
        stack.push(pre[j]);
        j++;
      }else {
        in[k]=stack.pop();
        k++;
      }
    }
    Node root = buildTree(pre, 0, n-1, in, 0, n-1);
    PrintPost(root);
//    System.out.println(post.size());
    for(int i=0;i<post.size();i++) {
      if(i==0) System.out.print(post.get(i));
      else System.out.print(" "+post.get(i));
    }
    
    
  }
  //根据前序与中序创建二叉树模板
  public static Node buildTree(int pre[],int pbegin,int pend,int in[],int ibegin,int iend) {
    if(pbegin>pend||ibegin>iend) return null;
    Node root = new Node(pre[pbegin]);//根节点
    for(int i=ibegin;i<=iend;i++) {
      if(pre[pbegin]==in[i]) {
        root.left = buildTree(pre, pbegin+1, pbegin-ibegin+i, in, ibegin, i-1);
        root.right = buildTree(pre, pbegin-ibegin+i+1, pend, in, i+1, iend);
      }
    }
    return root;
  }
  //后序遍历
  public static void PrintPost(Node root) { 
    if(root!=null) {
      PrintPost(root.left);
      PrintPost(root.right);
      post.add(root.element);
    }
  }

}
class Node{   //树节点类
  public int element; //节点值   
  public Node left;  //左右节点
  public Node right;
  
  public Node(int element) {
    // TODO Auto-generated constructor stub
    this.element = element;
    left = right = null;
  }
}

相关文章
|
2天前
|
机器学习/深度学习 Java 开发者
Python vs. Java:语言之争的终结
【6月更文挑战第8天】Python与Java,两种影响力巨大的编程语言,各有千秋。Python以简洁语法和强大库支持在数据科学、机器学习领域大放异彩,适合快速原型设计;而Java以其稳定性能、跨平台兼容性在大型系统、企业应用中占据一席之地。语言之争实为互补,开发者应根据项目需求选择合适工具,两者和谐共存,共同推动编程技术进步。
|
3天前
|
存储 设计模式 Java
Java语言中反射动态代理接口的解释与演示
Java语言中反射动态代理接口的解释与演示
5 1
|
4天前
|
算法 Java API
Base64编码介绍及基于Java语言实现
Base64编码介绍及基于Java语言实现
6 0
|
5天前
|
算法 Java Go
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
5 0
|
5天前
|
Java 容器
双指针(JAVA语言)
双指针(JAVA语言)
双指针(JAVA语言)
|
5天前
|
存储 算法 Java
【经典算法】LeetCode101:对称二叉树(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode101:对称二叉树(Java/C/Python3实现含注释说明,Easy)
7 1
|
5天前
|
JavaScript 前端开发 Java
Go语言入门【java->go】
Go语言入门【java->go】
16 2
|
6天前
|
JavaScript Java 测试技术
基于springboot+vue.js+uniapp小程序的java语言的考试信息报名系统附带文章源码部署视频讲解等
基于springboot+vue.js+uniapp小程序的java语言的考试信息报名系统附带文章源码部署视频讲解等
12 0
树的遍历:迭代 & 递归|Java 刷题打卡
树的遍历:迭代 & 递归|Java 刷题打卡
|
3天前
|
安全 Java 编译器
JAVA-多线程知识点总结(二)
JAVA-多线程知识点总结(二)