HihoCoder 1049 가장 상세한 문제 풀이 보고서
문제 풀이 사고방식: 처음에 나는 먼저 선서, 중서를 통해 두 갈래 나무를 구한 다음에 두 갈래 나무를 두루 훑어보는 것만 알았다. 이것은 당연히 문제 풀이 사고방식이지만 쓸모가 없다. 예를 들어 두 갈래 나무를 계산하는 것이다.사실 선순 서열과 중순 서열을 통해 후순 서열을 직접 구할 수 있다.사고방식은 다음과 같다.
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 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.