HihoCoder 1049 가장 상세한 문제 풀이 보고서

3855 단어
제목 출처: 뒷차례 두루 훑어보다
문제 풀이 사고방식: 처음에 나는 먼저 선서, 중서를 통해 두 갈래 나무를 구한 다음에 두 갈래 나무를 두루 훑어보는 것만 알았다. 이것은 당연히 문제 풀이 사고방식이지만 쓸모가 없다. 예를 들어 두 갈래 나무를 계산하는 것이다.사실 선순 서열과 중순 서열을 통해 후순 서열을 직접 구할 수 있다.사고방식은 다음과 같다.
1. 선행 서열의 첫 번째 노드를 루트 노드로 취한다.
2. 중간 시퀀스에서 루트 노드의 아래 표를 찾아 중간 시퀀스를 left와right 두 부분으로 나눈다.
3. left와right의 길이에 따라 선순 서열의 루트 노드의 좌우 아이를 계산한다.
4. 순서대로 왼쪽 아이, 오른쪽 아이를 계산하고 왼쪽 아이+오른쪽 아이+뿌리 노드로 돌아간다.
 
구체적인 알고리즘(Java Edition, 직접 AC)
 1 import java.util.Scanner;
 2 
 3 public class Main {
 4 
 5     public static String post_order(String preOrder,String inOrder){
 6         if(preOrder.length()>0&&preOrder.length()==inOrder.length()){
 7             char root=preOrder.charAt(0); // 
 8             int index=inOrder.indexOf(root); // 
 9             if(index!=-1){
10                 String left=inOrder.substring(0, index);// 
11                 String right=inOrder.substring(index+1);// 
12                 // + + 
13                 return post_order(preOrder.substring(1, left.length()+1),left)
+post_order(preOrder.substring(left.length()+1),right)
+root; 14 } 15 } 16 return ""; 17 } 18 19 public static void main(String[] args) { 20 Scanner scanner=new Scanner(System.in); 21 System.out.println(post_order(scanner.next(),scanner.next())); 22 } 23 }

좋은 웹페이지 즐겨찾기