[Java] 1020. Tree Traversals (25)-PAT甲级

1020. Tree Traversals (25)

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

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 postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. 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:

7

2 3 1 5 7 6 4

1 2 3 4 5 6 7

Sample Output:

4 1 6 3 5 7 2

题目大意:给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

PS:感谢github用户 @fs19910227 提供的pull request~

import java.util.LinkedList;
import java.util.Scanner;
 
public class Main {
    static Scanner scanner = new Scanner(System.in);
 
    static class Node {
        int value;
        Node left;
        Node right;
 
        Node(int value) {
            this.value = value;
        }
 
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
 
    private static Node bulidTree() {
        int size = scanner.nextInt();
        int[] postOrder = new int[size];
        int[] inOrder = new int[size];
        for (int i = 0; i < size; i++) {
            postOrder[i] = scanner.nextInt();
        }
        for (int i = 0; i < size; i++) {
            inOrder[i] = scanner.nextInt();
        }
        Node root = build(postOrder, inOrder,
                0, size - 1,
                0, size - 1);
        return root;
    }
 
    private static Node build(int[] postOrder, int[] inOrder, int postStart, int postEnd, int inStart, int inEnd) {
        if (postStart > postEnd) {
            return null;
        }
        if (postStart == postEnd) {
            return new Node(postOrder[postStart]);
        }
        int root = postOrder[postEnd--];
 
        //find root in inOrder
        int inIndex = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (root == inOrder[i]) {
                inIndex = i;
                break;
            }
        }
        //recursion build
        int leftSize = inIndex - inStart;
        int rightSize = inEnd - inIndex;
        Node rootNode = new Node(root);
        rootNode.left = build(postOrder, inOrder,
                postStart, postStart + leftSize - 1,
                inStart, inIndex - 1);
        rootNode.right = build(postOrder, inOrder, postEnd - rightSize + 1, postEnd, inIndex + 1, inEnd);
        return rootNode;
    }
 
    public static void main(String[] args) {
        Node root = bulidTree();
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
            System.out.printf("%d%s", poll.value, queue.isEmpty() ? "/n" : " ");
        }
    }
}

[Java] 1020. Tree Traversals (25)-PAT甲级

(随着网站访问量的激增,服务器配置只得一再升级以维持网站不“404 Not Found”,所以网站的维护费用也在不断上涨……(目前的阿里云服务器ECS+数据库RDS+域名购买+七牛云的费用是2200元/年),为了能不放弃该网站,所以我又把打赏链接放上来啦~所有打赏金额都会被记账并投入博客维护中,感谢厚爱,多多关照~)

原文 

https://www.liuchuo.net/archives/4991

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » [Java] 1020. Tree Traversals (25)-PAT甲级

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址