JAva:シーケンス配列を求める(中シーケンス遍歴と後シーケンス遍歴前シーケンス遍歴を探し、dfs(ツリーの検索)もある)

6814 ワード

JAva:順序付けを求める
タイトル
    
                 。        。(               ,  <=8)。
    
    ,       ,           
    
       ,        

      
  BADC
  BDCA
    
ABCD

参照:https://blog.csdn.net/a1439775520/article/details/92798355?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522158488090119724839256194%2522%252C%2522scm%2522%253A%252220140713.130056874…%2522%257D&request_id=158488090119724839256194&biz_id=0&utm_source=distribute.pc_search_result.none-task
解析
後の順序の最後のノードは必ず先の順序の最初のノードである.ルートノードが分かれば,左サブツリーと右サブツリーを中系列で分割できる.左右のサブツリーを再帰的に処理すると,先順遍歴の結果が得られる.mid,back,pre配列でそれぞれ中序,後序,先序を表す.
import java.util.Scanner;

public class       {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		String mid=sc.next();
		String back=sc.next();
		makeTree(mid,back);
	}
	//      
	public static void makeTree(String mid,String back){
		char root=back.charAt(back.length()-1);//             
		System.out.print(root);
		//              
		int rootInMid=mid.indexOf(root);
		//    
		if(rootInMid>0){
			//                 ,                   ,rootInMid   
			makeTree(mid.substring(0,rootInMid),back.substring(0,rootInMid));
		}
		//    
		if(rootInMid<mid.length()-1){
			makeTree(mid.substring(rootInMid+1),back.substring(rootInMid,back.length()-1));
		}
	}

}