在面試時，避免不了的會遇到一些資料結構的面試題，今天我們就來了解一下二叉樹的經典面試題：
已知二叉樹的前序周遊順序為ABDCEGHF，中序周遊順序為DBAGEHCF，求該二叉樹的後序周遊。
還有：
已知二叉樹的中序周遊順序為DBAGEHCF，後序周遊順序為DBGHEFCA，求該二叉樹的前序周遊。
類似的面試題應該如何應對呢？
文章持續更新，微信搜尋「
萬貓學社第一時間閱讀，關注後回複「
電子書」，免費擷取12本Java必讀技術書籍。
什麼是二叉樹？
在開始之前，容我再唠叨幾句：什麼是二叉樹？二叉樹（Binary Tree）是一種特殊的樹，樹上的每個結點最多有兩個子樹的樹結構，也就是說每一個父結點最多長出兩個樹杈。通常兩個子結點被稱為左子結點和右子結點。比如：
其中，A就是整個二叉樹的根結點，那麼B就是A的左子結點，C就是A的右子結點。每一個結點，我們可以用Java語言這樣實作：
/**
* 二叉樹結點
*/
public class TreeNode {
public char value;
/**
* 左子樹
*/
public TreeNode left;
/**
* 右子樹
*/
public TreeNode right;
}
三種周遊方式
在解題之前，先把先序周遊、中序周遊、後序周遊這三種周遊方式說清楚，為之後的解題打下良好的基礎。
先序周遊
先序周遊就是，先通路根結點，再通路左子結點，再通路右子結點。上圖二叉樹的先序周遊的順序就是ABDCEGHF。我們可以用Java語言這樣實作：
public void preOrder(TreeNode biTree) {
System.out.println(biTree.value);
if(biTree.left != null) {
preOrder(biTree.left);
}
if(biTree.right != null) {
preOrder(biTree.right);
}
}
中序周遊
先序周遊就是，先通路左子結點，再通路根結點，再通路右子結點。上圖二叉樹的中序周遊的順序就是DBAGEHCF。我們可以用Java語言這樣實作：
public void preOrder(TreeNode biTree) {
if(biTree.left != null) {
preOrder(biTree.left);
}
System.out.println(biTree.value);
if(biTree.right != null) {
preOrder(biTree.right);
}
}
後序周遊
先序周遊就是，先通路左子結點，再通路右子結點，再通路根結點。上圖二叉樹的後序周遊的順序就是DBGHEFCA。我們可以用Java語言這樣實作：
public void preOrder(TreeNode biTree) {
if(biTree.left != null) {
preOrder(biTree.left);
}
System.out.println(biTree.value);
if(biTree.right != null) {
preOrder(biTree.right);
}
}
經過上面的叙述，可以總結出：先序周遊、中序周遊、後序周遊三種周遊中的“先”、“中”、“後”都是指根結點的通路順序，“先”則是先通路根結點，“中”則是在左右中間通路根結點，，“後”則是最後通路根結點。
已知前中序周遊順序，求後序周遊順序
扯了這麼多，還是回到剛剛的第一道面試題上：
我們的解題思路是，先根據前中序周遊順序重新構造出這個二叉樹，再根據二叉樹寫出後序周遊順序。
重構二叉樹
前序周遊（ABDCEGHF）中的第一個結點A肯定為根結點，那麼在中序周遊（DBAGEHCF）中，A結點的左邊（DB）肯定為結點A的左子樹，A結點的右邊（GEHCF）肯定為結點A的右子樹，初步判斷二叉樹是這樣的：
再看A的左子樹（DB），在前序周遊（ABDCEGHF）中，B在最前面，說明B為該子樹的根結點，再看中序周遊（DBAGEHCF），B的左邊（D）肯定為A的左子樹，B的右邊（無）肯定為A的右子樹，初步判斷二叉樹是這樣的：
再看A的右子樹（GEHCF），在前序周遊（ABCDEGHF）中，C在最前面，說明C為該子樹的根結點，再看中序周遊（DBAGEHCF），C的左邊（GEH）肯定為C的左子樹，C的右邊（F）肯定為C的右子樹，初步判斷二叉樹是這樣的：
再看C的左子樹（GEH），在前序周遊（ABDCEGHF）中，E在最前面，說明E為該子樹的根結點，再看中序周遊（DBAGEHCF），E的左邊（G）肯定為E的左子樹，E的右邊（H）肯定為E的右子樹，可以最終判斷出二叉樹是這樣的：
寫出後序周遊順序
這個步驟就比較容易了，根據二叉樹得到的後序周遊順序就是：DBGHEFCA
已知中後序周遊順序，求前序周遊順序
我們的解題思路是，先根據中後序周遊順序重新構造出這個二叉樹，再根據二叉樹寫出前序周遊順序。
後序周遊（DBGHEFCA）中的最後一個結點A肯定為根結點，那麼在中序周遊（DBAGEHCF）中，A結點的左邊（DB）肯定為結點A的左子樹，A結點的右邊（GEHCF）肯定為結點A的右子樹，初步判斷二叉樹是這樣的：
再看A的左子樹（DB），在後序周遊（DBGHEFCA）中，B在最後面，說明B為該子樹的根結點，再看中序周遊（DBAGEHCF），B的左邊（D）肯定為A的左子樹，B的右邊（無）肯定為A的右子樹，初步判斷二叉樹是這樣的：
再看A的右子樹（GEHCF），在後序周遊（DBGHEFCA）中，C在最後面，說明C為該子樹的根結點，再看中序周遊（DBAGEHCF），C的左邊（GEH）肯定為C的左子樹，C的右邊（F）肯定為C的右子樹，初步判斷二叉樹是這樣的：
再看C的左子樹（GEH），在後序周遊（DBGHEFCA）中，E在最後面，說明E為該子樹的根結點，再看中序周遊（DBAGEHCF），E的左邊（G）肯定為E的左子樹，E的右邊（H）肯定為E的右子樹，可以最終判斷出二叉樹是這樣的：
這個步驟就比較容易了，根據二叉樹得到的前序周遊順序就是：ABDCEGHF
微信公衆号：萬貓學社
微信掃描二維碼
關注後回複「電子書」
擷取12本Java必讀技術書籍
作者：萬貓學社
出處：http://www.cnblogs.com/heihaozi/
版權聲明：本文遵循 CC 4.0 BY-NC-SA 版權協定，轉載請附上原文出處連結和本聲明。
微信掃描二維碼，關注
，回複「