一面

概述：一面來說還是比較簡單的了，面試官也比較和藹，問了一些簡單的java基礎，問了一下項目。

int和integer的差別

int是基本資料類型，存儲到方法區裡面，占用了4個位元組，初始值為0

integer是引用資料類型，存儲在堆裡面，初始值為null，對于-128到127之間的數，會進行緩存。關于integer的記憶體，有兩種推論，一種把堆分為兩部分：一部分為句柄池，另一部分為對象池。每個執行個體引用都是一個指向句柄池的本地指針，句柄池由指向對象池和類資料的兩個指針組成；對象池中隻存執行個體資料。這種表示法的優點是 gc時候，清理完垃圾對象後，還要整理碎片，就需要把非垃圾對象拷貝到一個新的區域，此時由于拷貝，新對象的位址已經改變，但并不需要指向對象的引用值做改變，隻用改變句柄池中指向對象池的引用位址即可；缺點是每次通路對象都需要經過兩次指針跳轉，效率較低。第二種是對象指針指向一組資料，這組資料本身包含有執行個體資料和指向類資料的指針。優缺點跟第一種方案相反。通過以上分析可得，Integer在記憶體中有一個指向方法區裡邊類資訊的指針，這個指針占用4bytes；另外Integer中執行個體變量隻有一個int類型的字段，是以為32位，4bytes。在不考慮lock、wait set、gc相關資訊占用的時候，如果是第一種方案，有4bytes的指向對象池的指針，一共是34=12bytes；如果是第二種實作方案，則是24-8bytes的指針。我們怎麼能确定jvm用的是第一種方案還是第二種方案呢？lock、wait set、gc相關資訊在僅僅建立，累加，銷毀的時候是否的确不存在呢？從VisualVM生成的heap dump檔案分析，每個Integer占用了3*4bytes：一般來說JVM的Integer占用8bytes

//對于兩個非new生成的Integer對象，進行比較時，如果兩個變量的值在區間-128到127之間，則比較結果為true，如果兩個變量的值不在此區間，則比較結果為false
Integer i1 = 127;//java在編譯的時候,被翻譯成-> Integer i5 = Integer.valueOf(127);
Integer i2 = 127;//在緩存中取得127是以為true
System.out.println(i1 == i2);//true
Integer i3 = 128;
Integer i4 = 128;//沒有緩存了，隻能new
System.out.println(i3 == i4);//false
 
//JDK源碼的valueOf函數式這樣的：
public static Integer valueOf(int i) {
      assert IntegerCache.high >= 127;
      if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
}

jvm的垃圾收集器

Serial 串行垃圾回收器

單線程新生代收集器，隻會用一條線程完成收集工作在Client模式下的虛拟機可以選擇，新生代：複制算法。老年代：标記—整理

ParNew

Serial的多線程版本，收集過程以及算法與Serival一緻，可與CMS老年代收集器配合

Serial Old

Serial 的老年代版本，采用标記—整理

Parallel Scavenge 并行垃圾回收器

新生代收集器，多線程，主要關注吞吐量，适合在背景運算不需要太多互動的任務，采用複制算法

Parallel Old

Parallel Scavenge的老年代版本，采用多線程标記—整理

CMS 并發标記掃描垃圾回收器

老年代收集器，關注停頓時間，采用标記—清除。4個過程，初始标記，并發标記，重新标記，并發清除。收集過程與使用者線程并發執行，缺點：并發收集占用CPU資源，降低吞吐率。浮動垃圾，程式不斷運作會産生新的垃圾。JDK1.5老年代占用達到68%會觸發，JDK1.6老年代占用達到92%會觸發，觸發的門檻值可以設定，設定不當會導緻FuLL GC 降低性能。會出現記憶體碎片，可設定參數，多少次不壓縮的Full GC之後，進行一次壓縮的，預設0，每次都會壓縮。

G1 G1垃圾回收器

特點：并行與并發，分代收集，空間整合，可預測的停頓将Java堆分為多個大小相等的獨立區域，跟蹤每個區域裡垃圾的價值，維護一個優先清單，優先回收價值最大的。區域空間對象的引用使用Remembered Set記錄，如果引用的對象處于不同的區域，通過Card Table把引用資訊記錄到被引用對象的Remembered Set中。過程：初始标記，并發标記，最終标記，篩選回收

動态代理

動态代理分為兩種：jdk動态代理是由java内部的反射機制來實作的；cglib動态代理底層則是借助asm來實作的。總的來說，反射機制在生成類的過程中比較高效，而asm在生成類之後的相關執行過程中比較高效。還有一點必須注意：jdk動态代理的應用前提，必須是目标類基于統一的接口。如果沒有上述前提，jdk動态代理不能應用。由此可以看出，jdk動态代理有一定的局限性，cglib這種第三方類庫實作的動态代理應用更加廣泛，且在效率上更有優勢。。

IOC和DI

Ioc—Inversion of Control，即“控制反轉”，不是什麼技術，而是一種設計思想。在Java開發中，Ioc意味着将你設計好的對象交給容器控制，而不是傳統的在你的對象内部直接控制。

　誰控制誰，控制什麼：傳統Java SE程式設計，我們直接在對象内部通過new進行建立對象，是程式主動去建立依賴對象；而IoC是有專門一個容器來建立這些對象，即由Ioc容器來控制對象的建立；誰控制誰？當然是IoC 容器控制了對象；控制什麼？那就是主要控制了外部資源擷取（不隻是對象包括比如檔案等）。

　　為何是反轉，哪些方面反轉了：有反轉就有正轉，傳統應用程式是由我們自己在對象中主動控制去直接擷取依賴對象，也就是正轉；而反轉則是由容器來幫忙建立及注入依賴對象；為何是反轉？因為由容器幫我們查找及注入依賴對象，對象隻是被動的接受依賴對象，是以是反轉；哪些方面反轉了？依賴對象的擷取被反轉了。

　　用圖例說明一下，傳統程式設計如圖2-1，都是主動去建立相關對象然後再組合起來：

美團Java開發實習生面經一面二面三面

DI—Dependency Injection，即“依賴注入”：元件之間依賴關系由容器在運作期決定，形象的說，即由容器動态的将某個依賴關系注入到元件之中。依賴注入的目的并非為軟體系統帶來更多功能，而是為了提升元件重用的頻率，并為系統搭建一個靈活、可擴充的平台。

了解DI的關鍵是：“誰依賴誰，為什麼需要依賴，誰注入誰，注入了什麼”，那我們來深入分析一下：

　　誰依賴于誰：當然是應用程式依賴于IoC容器；

　　為什麼需要依賴：應用程式需要IoC容器來提供對象需要的外部資源；

　　誰注入誰：很明顯是IoC容器注入應用程式某個對象，應用程式依賴的對象；

　　注入了什麼：就是注入某個對象所需要的外部資源（包括對象、資源、常量資料）。

index索引

資料庫索引，是資料庫管理系統中一個排序的資料結構，以協助快速查詢、更新資料庫表中資料。索引的實作通常使用B樹及其變種B+樹。設定索引要付出代價的：一是增加了資料庫的存儲空間，二是在插入和修改資料時要花費較多的時間(因為索引也要随之變動)。

優點：

第一，通過建立唯一性索引，可以保證資料庫表中每一行資料的唯一性。
第二，可以大大加快資料的檢索速度，這也是建立索引的最主要的原因。
第三，可以加速表和表之間的連接配接，特别是在實作資料的參考完整性方面特别有意義。
第四，在使用分組和排序子句進行資料檢索時，同樣可以顯著減少查詢中分組和排序的時間。
第五，通過使用索引，可以在查詢的過程中，使用優化隐藏器，提高系統的性能。

缺點：

第一，建立索引和維護索引要耗費時間，這種時間随着資料量的增加而增加。
第二，索引需要占實體空間，除了資料表占資料空間之外，每一個索引還要占一定的實體空間，如果要建立聚簇索引，那麼需要的空間就會更大。
第三，當對表中的資料進行增加、删除和修改的時候，索引也要動态的維護，這樣就降低了資料的維護速度。

索引使用的場景：

在經常需要搜尋的列上，可以加快搜尋的速度；
在作為主鍵的列上，強制該列的唯一性群組織表中資料的排列結構；
在經常用在連接配接的列上，這些列主要是一些外鍵，可以加快連接配接的速度；
在經常需要根據範圍進行搜尋的列上建立索引，因為索引已經排序，其指定的範圍是連續的；
在經常需要排序的列上建立索引，因為索引已經排序，這樣查詢可以利用索引的排序，加快排序
查詢時間；在經常使用在WHERE子句中的列上面建立索引，加快條件的判斷速度。

不應該使用索引的場景：

第一，對于那些在查詢中很少使用或者參考的列不應該建立索引。這是因為，既然這些列很少使用到，是以有索引或者無索引，并不能提高查詢速度。相反，由于增加了索引，反而降低系統的維護速度和增大了空間需求。
第二，對于那些隻有很少資料值的列也不應該增加索引。這是因為，由于這些列的取值很少，例如人事表的性别列，在查詢的結果中，結果集的資料行占了表中資料行的很大比例，即需要在表中搜尋的資料行的比例很大。增加索引，并不能明顯加快檢索速度。
第三，對于那些定義為text, image和bit資料類型的列不應該增加索引。這是因為，這些列的資料量要麼相當大，要麼取值很少。
第四，當修改性能遠遠大于檢索性能時，不應該建立索引。這是因為，修改性能和檢索性能是互相沖突的。當增加索引時，會提高檢索性能，但是會降低修改性能。當減少索引時，會提高修改性能，降低檢索性能。是以，當修改性能遠遠大于檢索性能時，不應該建立索引。

索引種類

唯一索引、主鍵索引和聚集索引。

B樹和B+樹

1）B樹

B樹中每個節點包含了鍵值和鍵值對于的資料對象存放位址指針，是以成功搜尋一個對象可以不用到達樹的葉節點。成功搜尋包括節點内搜尋和沿某一路徑的搜尋，成功搜尋時間取決于關鍵碼所在的層次以及節點内關鍵碼的數量。在B樹中查找給定關鍵字的方法是：首先把根結點取來，在根結點所包含的關鍵字K1,…,kj查找給定的關鍵字（可用順序查找或二分查找法），若找到等于給定值的關鍵字，則查找成功；否則，一定可以确定要查的關鍵字在某個Ki或Ki+1之間，于是取Pi所指的下一層索引節點塊繼續查找，直到找到，或指針Pi為空時查找失敗。

2）B+樹

B+樹非葉節點中存放的關鍵碼并不訓示資料對象的位址指針，非葉節點隻是索引部分。所有的葉節點在同一層上，包含了全部關鍵碼和相應資料對象的存放位址指針，且葉節點按關鍵碼從小到大順序連結。如果實際資料對象按加入的順序存儲而不是按關鍵碼次數存儲的話，葉節點的索引必須是稠密索引，若實際資料存儲按關鍵碼次序存放的話，葉節點索引時稀疏索引。B+樹有2個頭指針，一個是樹的根節點，一個是最小關鍵碼的葉節點。是以 B+樹有兩種搜尋方法：一種是按葉節點自己拉起的連結清單順序搜尋。一種是從根節點開始搜尋，和B樹類似，不過如果非葉節點的關鍵碼等于給定值，搜尋并不停止，而是繼續沿右指針，一直查到葉節點上的關鍵碼。是以無論搜尋是否成功，都将走完樹的所有層。B+ 樹中，資料對象的插入和删除僅在葉節點上進行。

這兩種處理索引的資料結構的不同之處：

a，B樹中同一鍵值不會出現多次，并且它有可能出現在葉結點，也有可能出現在非葉結點中。而B+樹的鍵一定會出現在葉結點中，并且有可能在非葉結點中也有可能重複出現，以維持B+樹的平衡。
b，因為B樹鍵位置不定，且在整個樹結構中隻出現一次，雖然可以節省存儲空間，但使得在插入、删除操作複雜度明顯增加。B+樹相比來說是一種較好的折中。
c，B樹的查詢效率與鍵在樹中的位置有關，最大時間複雜度與B+樹相同(在葉結點的時候)，最小時間複雜度為1(在根結點的時候)。而B+樹的時候複雜度對某建成的樹是固定的。

事務

1.事物的概念

1）什麼是事務

事務是對資料庫操作的最基本機關。事務是一組操作，要不全成功，要不全不成功
2）事務的特性

A:原子性(Atomicity)。事務是資料庫的邏輯工作機關，事務中包括的諸操作要麼全做，要麼全不做。

C:一緻性(Consistency) 事務執行的結果必須是使資料庫從一個一緻性

态變到另一個一緻性狀态。一緻性與原子性是密切相關的。

I:隔離性(Isolation) 一個事務的執行不能被其他事務幹擾。

D:持續性/永久性(Durability)一個事務一旦送出，它對資料庫中資料的改

變就應該是永久性的。
3）不考慮隔離性産生的問題

髒讀：髒讀是指在一個事務處理過程裡讀取了另一個未送出的事務中的資料

不可重複讀：不可重複讀發生在一個事務執行相同的查詢兩次或兩次以上，但是每次都得到不同的資料時。這通常是因為另一個并發事務在兩次查詢期間進行了更新。

幻讀：幻讀與不可重複讀類似。它發生在一個事務（T1）讀取了幾行資料，接着另一個并發事務（T2）插入了一些資料時。在随後的查詢中，第一個事務（T1）就會發現多了一些原本不存在的記錄。

幻讀和不可重複讀的差別：

不可重複讀的重點是修改:

幻讀的重點在于新增或者删除
4）解決3）中的問題、

設定隔離級别

ISOLATION_DEFAULT：使用後端資料庫預設的隔離級别

ISOLATION_READ_UNCOMMITTED：最低的隔離級别，允許讀取尚未送出的資料變更，可能會導緻髒讀、幻讀或不可重複讀

ISOLATION_READ_COMMITTED：允許讀取并發事務已經送出的資料，可以阻止髒讀，但是幻讀或不可重複讀仍有可能發生

ISOLATION_REPEATABLE_READ：對同一字段的多次讀取結果都是一緻的，除非資料是被本身事務自己所修改，可以阻止髒讀和不可重複讀，但幻讀仍有可能發生

ISOLATION_SERIALIZABLE：最高的隔離級别，完全服從ACID的隔離級别，確定阻止髒讀、不可重複讀以及幻讀，也是最慢的事務隔離級别，因為它通常是通過完全鎖定事務相關的資料庫表來實作的

hashmap在高并發時期會出現的問題

Rehash/再散列擴充内部數組長度

在哈希表使用的過程中不斷的對table容量進行調整，看一下put操作中的addEntry()方法：

void addEntry(int hash, K key, V value, int bucketIndex) {
   Entry<K,V> e = table[bucketIndex];
       table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
       if (size++ >= threshold)
           resize(2 * table.length);
   }

這裡面resize的過程，就是再散列調整table大小的過程，預設是目前table容量的兩倍。

void resize(int newCapacity) {
       Entry[] oldTable = table;
       int oldCapacity = oldTable.length;
       if (oldCapacity == MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return;
       }
 
       Entry[] newTable = new Entry[newCapacity];
       //初始化一個大小為oldTable容量兩倍的新數組newTable
       transfer(newTable);
       table = newTable;
       threshold = (int)(newCapacity * loadFactor);
   }

關鍵的一步操作是transfer(newTable)，這個操作會把目前Entry[] table數組的全部元素轉移到新的table中，

這個transfer的過程在并發環境下會發生錯誤，導緻數組連結清單中的連結清單形成循環連結清單，在後面的get操作時e = e.next操作無限循環，Infinite Loop出現。

HashMap在多線程put後可能導緻get無限循環

多線程put的時候可能導緻元素丢失

那麼如何使用線程安全的哈希表結構呢，這裡列出了幾條建議：

使用Hashtable 類，Hashtable 是線程安全的；

使用并發包下的java.util.concurrent.ConcurrentHashMap，ConcurrentHashMap實作了更進階的線程安全；

或者使用synchronizedMap() 同步方法包裝 HashMap object，得到線程安全的Map，并在此Map上進行操作

在一個數組中找到最長的遞增序列

//時間複雜度為n
static int i=0,j=0;
	public static void main(String[] args) {
		int[] arr={1,2,3,4,2,3,4};
		System.out.println(cal_length(arr));
		
	}	
	public static int cal_length(int[] arr){
		int max=0;//記錄最長的序列長度
		int p=0,q;//p指向序列的開始，q指向p的下一個元素，如果是遞增的q++
		for(q=1;q<arr.length;++q){
			if (arr[q]<arr[q-1]) {//遞增序列結束
				if (q-1-p>max) {//判斷序列長度是否大于max
					i=p;
					j=q-1;
					max=j-i+1;
				}
				p=q;//将p重新指派為q的位置
			}else if (q==arr.length-1) {//q走到數組結束的時候
				if (q-p+1>max) {
					i=p;
					j=q;
					max=j-i+1;
				}
			}
		}
		return max;
	}

二面

概述：二面的面試官主要是問了最近有學習什麼知識，坑都是自己跳進去的。本人說了學習設計模式和JVM的相關知識，問了很多相關的内容，但是大部分時間面試官都是讓自己在描述。

B+樹和B樹的差別

索引原理

資料庫的搜尋引擎

首先介紹一下Innodb引擎。

Innodb引擎提供了對資料庫ACID事務的支援。并且還提供了行級鎖和外鍵的限制。它的設計的目标就是處理大資料容量的資料庫系統。它本身實際上是基于Mysql背景的完整的系統。Mysql運作的時候，Innodb會在記憶體中建立緩沖池，用于緩沖資料和索引。

接下來來說說MyIASM引擎。它是MySql的預設引擎，但不提供事務的支援，也不支援行級鎖和外鍵。是以當執行Insert插入和Update更新語句時，即執行寫操作的時候需要鎖定這個表。是以會導緻效率會降低。

我們在來說說這兩種引擎的選擇。其實上面已經提到了。這裡我在補充了兩點：

1、大容量的資料集時趨向于選擇Innodb。因為它支援事務處理和故障的恢複。Innodb可以利用資料日志來進行資料的恢複。主鍵的查詢在Innodb也是比較快的。
2、大批量的插入語句時（這裡是INSERT語句）在MyIASM引擎中執行的比較的快，但是UPDATE語句在Innodb下執行的會比較的快，尤其是在并發量大的時候。

最後我們再來說說兩種引擎所使用的索引的資料結構是什麼？答案是都是B+樹。

對于MyIASM引擎來說，B+樹的資料結構中存儲的内容實際上是實際資料的位址值。也就是說它的索引和實際資料是分開的，隻不過使用索引指向了實際資料。這種索引的模式被稱為非聚集索引。

而Innodb引擎的索引的資料結構也是B+樹，隻不過資料結構中存儲的都是實際的資料，這種索引有被稱為聚集索引。MyISAM 使用的是表鎖，而 InnoDB實作的是行鎖。

mysql優化

優化SQL和索引

優化資料庫對象

1）選擇表合适存儲引擎

2）優化表的資料類型,選擇合适的資料類型

應用優化

1)使用連接配接池

2)減少對mysql的通路，使用mem緩存等

3)負載均衡，複制分流查詢操作

分庫分表

1）水準劃分

如果某個表的資料太多，預期有上千條甚至上億以上，我們可以化整為0：拆表。

這裡就涉及到拆表的算法：

記錄日志的表，也可以按周或者按月來拆。

記錄使用者資訊的表，按使用者id的hash算法來拆。

2）垂直拆分

如果表記錄數并不多，可能也就2、3萬條，但是字段卻很長，表占用空間很大，檢索表時需要執行大量I/O，嚴重降低了性能。這個時候需要把大的字段拆分到另一個表，并且該表與原表是一對一的關系。

5.讀寫分離

讀寫分離，基本的原理是讓主資料庫處理事務性增、改、删操作（INSERT、UPDATE、DELETE），而從資料庫處理SELECT查詢操作。資料庫複制被用來把事務性操作導緻的變更同步到叢集中的從資料庫。

6.動态代理的實作原理

詳情

7.反射實作原理

在Java中的反射機制是指在運作狀态中，對于任意一個類，都能夠知道這個類的所有屬性和方法；對于任意一個類，都能調用它的任意一個方法；這種動态擷取資訊以及動态調用對象的功能成為Java語言的反射機制。 Java的反射機制的實作要借助于4個類：class，Constructor，Field，Method；其中class代表的時類對象，Constructor－類的構造器對象，Field－類的屬性對象，Method－類的方法對象。通過這四個對象我們可以粗略的看到一個類的各個組成部分。

8.泛型

9.程序之間的通信方式

管道( pipe )：管道是一種半雙工的通信方式，資料隻能單向流動，而且隻能在具有親緣關系的程序間使用。程序的親緣關系通常是指父子程序關系。有名管道 (named pipe) ：有名管道也是半雙工的通信方式，但是它允許無親緣關系程序間的通信。信号量( semophore ) ：信号量是一個計數器，可以用來控制多個程序對共享資源的通路。它常作為一種鎖機制，防止某程序正在通路共享資源時，其他程序也通路該資源。是以，主要作為程序間以及同一程序内不同線程之間的同步手段。消息隊列( message queue ) ：消息隊列是由消息的連結清單，存放在核心中并由消息隊列辨別符辨別。消息隊列克服了信号傳遞資訊少、管道隻能承載無格式位元組流以及緩沖區大小受限等缺點。信号 ( sinal ) ：信号是一種比較複雜的通信方式，用于通知接收程序某個事件已經發生。共享記憶體( shared memory ) ：共享記憶體就是映射一段能被其他程序所通路的記憶體，這段共享記憶體由一個程序建立，但多個程序都可以通路。共享記憶體是最快的 IPC 方式，它是針對其他程序間通信方式運作效率低而專門設計的。它往往與其他通信機制，如信号兩，配合使用，來實作程序間的同步和通信。套接字( socket ) ：套解口也是一種程序間通信機制，與其他通信機制不同的是，它可用于不同主機間的程序通信。

10.網絡的七層模型

應用層：主要指應用程式；表示層：用于資料格式交換、資料加解密、資料壓縮和恢複；會話層：用于建立、維持和斷開網絡會話；傳輸層：負責端到端（程序到程序）之間資料的傳輸控制；網絡層：傳送分組，主要負責主機到主機的資料傳輸以及分組的選路，實作路由選擇、擁塞控制、網絡互連的功能資料鍊路層：資料在一段鍊路上的相鄰結點間的傳輸。傳輸資料時，鍊路層将網絡層的資料封裝成幀（framing），進而實作以幀為傳輸機關，采用簡單的差錯控制方法，使有差錯的實體線路變成無差錯的資料鍊路。實體層：利用實體傳輸媒體為資料鍊路層提供實體連接配接，透明地傳輸比特流。

11.TCP和UDP的差別

UDP的主要特點

UDP是無連接配接的，即發送資料之前不需要建立連接配接

UDP使用盡最大努力傳遞，不保證可靠傳遞，同時也不使用擁塞控制。

UDP是面向封包的。UDP沒有擁塞控制，很适合多媒體通信的要求。

UDP支援一對一、一對多、多對一和多對多的互動通信。

UDP的首部開銷小，隻有8個位元組。

TCP 的主要特點：

TCP 是面向連接配接的運輸層協定。

應用程式在使用TCP協定之前，首先要建立TCP連接配接。資料傳輸完畢後，要釋放TCP連接配接。

每一條 TCP 連接配接隻能有兩個端點，TCP 連接配接隻能是點對點的。是以TCP不能進行廣播和多點傳播，UDP可以。

TCP 提供可靠傳遞的服務。通過TCP連接配接傳送的資料無差錯、不丢失、不重複、并且按序到達。

TCP 提供全雙工通信。

TCP是面向位元組流的。

在一個TCP連接配接中傳送的位元組流中的每一個位元組都按順序編号

三面

概述：三面主要是問了平時怎麼學習的，沒問什麼技術難點，最後問了一個資料結構的問題；已知一個二叉樹的中序周遊和後序周遊的結果，請輸出前序周遊的結果。

//全局變量存放後序序列
    //先寫根，後寫左子樹，最後寫右子樹
    public static String res = "";
   
    //進行周遊輸出
    //參數依此為中序序列，後序序列
    public static void cal_tree(String smid, String slast) {
        //boolean state = StringEquals(smid, slast);
       /* if (state == false)
            return;*/
        if (smid.length() == 0)
            return;
        //每次添加都是添加中序的字元，當中序字元串長度為1的時候，就傳回
        if (smid.length() == 1) {
            res += smid;
            return;
        }
        //後序序列中最後一個就是根
        char root = slast.charAt(slast.length()-1);
        //擷取字元在中序序列總的位置
        //mid代表的是索引
        int mid = smid.indexOf(root);
        //中序序列的左子樹
        String c=smid.substring(0, mid);
        //中序序列的右子樹
        String d = smid.substring(mid+1);
        //寫入根
        res += root;
        //中序左子樹，後序左子樹
        cal_tree(c,slast.substring(0, c.length()));
        //中序右子樹，後序右子樹,注意這裡後序的右子樹要最大為slast.length()-1
        cal_tree(d,slast.substring(c.length(),slast.length()-1));
       
    }
    public static void main(String[] agrs) {
        String s1 = "ADEFGHMZ";
        String s2 = "AEFDHZMG";
        cal_tree(s1, s2);
        if (res.length() != s1.length())
        {
            System.out.println("wrong tree list!");
        }
        else {
            System.out.println(res);
        }
    }