<a href="#%e5%89%91%e6%8c%87offer-%e7%ac%ac4%e7%ab%a0%e8%af%be%e5%90%8e%e9%a2%98%e8%af%a6%e8%a7%a3">劍指offer 第4章課後題詳解</a>
<a href="#%e7%9b%ae%e5%bd%95">目錄</a>
<a href="#%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e9%95%9c%e5%83%8f">二叉樹的鏡像</a>
<a href="#%e5%88%86%e6%9e%90">分析</a>
<a href="#%e8%a7%a3%e6%b3%95">解法</a>
<a href="#%e6%8b%93%e5%b1%95">拓展</a>
<a href="#%e5%88%a4%e6%96%ad%e5%89%8d%e5%ba%8f%e9%81%8d%e5%8e%86">判斷前序周遊</a>
<a href="#%e5%88%86%e6%9e%90-1">分析</a>
<a href="#%e8%a7%a3%e6%b3%95-1">解法</a>
<a href="#%e6%8b%93%e5%b1%95-1">拓展</a>
<a href="#%e5%ad%97%e7%ac%a6%e7%9a%84%e7%bb%84%e5%90%88">字元的組合</a>
<a href="#%e5%88%86%e6%9e%90-2">分析</a>
<a href="#%e8%a7%a3%e7%ad%94">解答</a>
<a href="#%e6%ad%a3%e6%96%b9%e4%bd%93%e7%9a%84%e9%a1%b6%e7%82%b9">正方體的頂點</a>
<a href="#%e5%88%86%e6%9e%90-3">分析</a>
<a href="#%e8%a7%a3%e6%b3%95-2">解法</a>
<a href="#8%e4%b8%aa%e7%9a%87%e5%90%8e">8個皇後</a>
<a href="#%e5%88%86%e6%9e%90-4">分析</a>
<a href="#%e8%a7%a3%e6%b3%95-3">解法</a>
本題為《劍指offer》“面試題19：二叉樹的鏡像”一節中的“本題拓展”。
請完成一個函數，輸入一個二叉樹，該函數輸出它的鏡像，要求使用循環的方法，不能用遞歸。二叉樹節點定義如下：
仔細分析兩棵樹的特點，我們可以發現求二叉樹的鏡像等價于将每個非葉節點的左右子節點進行交換。要進行此操作，就需要對二叉樹進行周遊。二叉樹周遊的方式共有4種，前序周遊，中序周遊，後序周遊，層次周遊。由于需要交換左右子節點，前3種涉及左右子節點和根節點之間通路順序的周遊都不是特别适合。這裡采用的是層次周遊。
如何廣度優先周遊一個有向圖的方法與層次周遊樹的方法大體一緻，隻有一點不同，圖有可能會通路到已經通路過的節點，是以需要判斷接下來通路的節點是否是已通路的。可以在圖節點結構中加一個bool類型的flag，或者使用輔助空間儲存已入隊的節點，在每個節點加入到隊列之前先進行判定是否已經加入過隊列。
本題為《劍指offer》“面試題24：二叉樹的後序周遊序列”一節中的“相關題目”。
輸入一個整數數組，判斷該數組是不是某二叉搜尋樹的前序周遊的結果。假設輸入數組的任意兩個數字都不相等。
二叉搜尋樹定義，根節點的值小于左子節點的值（如果存在），大于右子節點的值（如果存在），且左右子樹都為二叉搜尋樹，注意：空樹也是二叉搜尋樹。
首先分析二叉搜尋樹的特點，二叉搜尋樹中，所有父節點的值都大于左子數中任意節點的值（如果存在），小于右子數中任意節點的值（如果存在）。再結合前序周遊的特點，數組中的第一個數必然是根節點的值，然後向後依次周遊數組中的數，找到第一個大于根節點值的數，則在這個數左邊的元素都是根節點左子樹中節點的值，而這個數以及它右邊的元素都是跟節點右子樹中節點的值（還需要再檢查一遍是否都大于根節點的值）。根據同樣的道理，再對左右子樹進行遞歸檢查。
輸入一個整數數組，判斷該數組是不是某二叉搜尋樹的中序周遊的結果。假設輸入數組的任意兩個數字都不相等。
等價于
輸入一個整數數組，判斷該數組是不是有序遞增的。假設輸入數組的任意兩個數字都不相等。
本題為《劍指offer》“面試題28：字元串的排列”一節中的“本題拓展”。
輸入一個字元串，列印出該字元串中所有的組合，例如輸入三個字元a，b，c，則它們的組合有a，b，c，ab，ac，bc，abc。而ab和ba隻能算一個組合。假設輸入的字元串中字元均不同（原題雖然沒有這一條限定，但從原題的分析和解答中可以推測出有這一條限定）
如果輸入n個字元，則這n個字元可以構成長度從1~n的組合。用n個字元構成長度為1的組合，共n種情況，即每個組合隻包含n個字元中的任何1個字元。用n個字元構成長度為n的組合，隻有1中情況，即組合包含全部n個字元。這兩種特例可以作為遞歸的結束。而用n個字元構成長度為m（1
本題為《劍指offer》“面試題28：字元串的排列”一節中的“相關題目”。
輸入一個含有8個數字的數組，判斷有沒有可能把這個8個數字分别放到正方體的8個頂點上，使得正方體上三組相對的面上的4個頂點的和都相等。
可以先求出a1-a8這8個數字的所有排列，然後判斷有沒有某一個的排列符合題目設定的條件，即a1+a2+a3+a4 = a5+a6+a7+a8,且a1+a3+a5+a7 = a2+a4+a6+a8，且a1+a2+a5+a6=a3=a4+a7+a8。求8個數字的排列和“面試題28：字元串的排列”中求字元串的排列類似，可以将求8個數字的排列的問題分解下，将8個數字中的1個輪流固定放在數組的第一個位置，然後求剩下7個數字的排列，再依次遞歸下去。
在8 x 8的國際象棋上擺放8個皇後，使其不能互相攻擊，即任意兩個皇後不得處在同一行、同一列或者同一對角線上。請問總共有多少種符合條件的擺法。
可以定義一個含有8個數字0~7的數組，數組下标表示行号，數組元素的值表示列号，這樣任意順序的數組都可以符合皇後不能擺在同一行同一列的要求。再把所有的排列求出來，計算其中符合不在同一對角線的要求的排列數。
本題大多數代碼都與上題一緻，隻有全局變量和判定函數不同。具體求出所有排列的算法可以參照上題。