[劍指Offer] 第4章課后題詳解

目錄

二叉樹的鏡像

本題為《劍指Offer》“面試題19：二叉樹的鏡像”一節中的“本題拓展”。

請完成一個函數，輸入一個二叉樹，該函數輸出它的鏡像，要求使用循環的方法，不能用遞歸。二叉樹節點定義如下：

struct BinaryTreeNode{
    int             m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

分析

仔細分析兩棵樹的特點，我們可以發現求二叉樹的鏡像等價于將每個非葉節點的左右子節點進行交換。要進行此操作，就需要對二叉樹進行遍歷。二叉樹遍歷的方式共有4種，前序遍歷，中序遍歷，后序遍歷，層次遍歷。由于需要交換左右子節點，前3種涉及左右子節點和根節點之間訪問順序的遍歷都不是特別適合。這里采用的是層次遍歷。

解法

//使用容器適配器queue，《劍指Offer》中第23題用的是deque實現層次遍歷，但個人覺得不需要，deque的雙端進出和隨機訪問都沒用到，這里只需要一個能實現先進先出的容器就足夠了。
#include <queue>

auto MirrorRecursively(BinaryTreeNode *pRoot) -> void{

    //處理空樹
    if(pRoot == NULL){
        return;
    }

    queue<BinaryTreeNode*> queueTreeNode;
    //將根節點加入到隊列中
    queueTreeNode.push(pRoot);

    while(!queueTreeNode.empty()){
        //取出隊頭的節點
        BinaryTreeNode *pNode = queueTreeNode.front();
        queueTreeNode.pop();

        //其實不加此判定也可以正常運行，葉節點的左右子節點都為空，進行交換后也不會有任何影響，只是會多進行幾次操作，在葉節點數量較大時可能會對算法性能造成影響。
        if(pNode -> m_pLeft == NULL && pNode -> m_pRight == NULL){
            continue;
        }

        //如果左子樹不為空，將左子樹的根節點加入到隊列中
        if(pNode -> m_pLeft){
            queueTreeNode.push(pNode -> m_pLeft);
        }

        //如果右子樹不為空，將右子樹的根節點加入到隊列中
        if(pNode -> m_pRight){
            queueTreeNode.push(pNode -> m_pRight);
        }

        //交換左右子樹
        BinaryTreeNode* tmp = pNode -> m_pLeft;
        pNode -> m_pLeft = pNode -> m_pRight;
        pNode -> m_pRight = tmp;
    }
}

拓展

如何廣度優先遍歷一個有向圖的方法與層次遍歷樹的方法大體一致，只有一點不同，圖有可能會訪問到已經訪問過的節點，所以需要判斷接下來訪問的節點是否是已訪問的。可以在圖節點結構中加一個bool類型的flag，或者使用輔助空間保存已入隊的節點，在每個節點加入到隊列之前先進行判定是否已經加入過隊列。

判斷前序遍歷

本題為《劍指Offer》“面試題24：二叉樹的后序遍歷序列”一節中的“相關題目”。

輸入一個整數數組，判斷該數組是不是某二叉搜索樹的前序遍歷的結果。假設輸入數組的任意兩個數字都不相等。

分析

二叉搜索樹定義，根節點的值小于左子節點的值（如果存在），大于右子節點的值（如果存在），且左右子樹都為二叉搜索樹，注意：空樹也是二叉搜索樹。

首先分析二叉搜索樹的特點，二叉搜索樹中，所有父節點的值都大于左子數中任意節點的值（如果存在），小于右子數中任意節點的值（如果存在）。再結合前序遍歷的特點，數組中的第一個數必然是根節點的值，然后向后依次遍歷數組中的數，找到第一個大于根節點值的數，則在這個數左邊的元素都是根節點左子樹中節點的值，而這個數以及它右邊的元素都是跟節點右子樹中節點的值（還需要再檢查一遍是否都大于根節點的值）。根據同樣的道理，再對左右子樹進行遞歸檢查。

解法

auto VerifySquenceOfBST(const int sequence[], const unsigned length) -> bool{

    //這里原書類似的判斷后續遍歷的算法返回的是false，但個人覺得應該是返回true，根據搜索二叉樹定義，空樹也是二叉搜索樹！
    if(sequence == NULL || length == 0){
        return true;
    }

    //數組的第一個元素為根節點的值
    int root = sequence[0];

    //從第二個元素開始，依次尋找第一個大于根節點值的元素
    int i = 1;
    for(;i < length ; ++i){
        if(sequence[i] > root){
            break;
        }
    }

    //判斷根節點右子樹上的所有節點的值是否都大于根節點的值
    int j = i;
    for(;j < length ; ++j){
        if(sequence[j] < root){
            return false;
        }
    }

    //如果左子樹不為空，遞歸判定左子樹是否為二叉搜索樹
    bool left = true;
    if(i > 1){
        left = VerifySquenceOfBST(sequence, i - 1);
    }

    //如果右子樹不為空，遞歸判定右子樹是否為二叉搜索樹
    bool right = true;
    if(i < length){
        right = VerifySquenceOfBST(sequence + i, length - i);
    }

    return (left && right);
}

拓展

輸入一個整數數組，判斷該數組是不是某二叉搜索樹的中序遍歷的結果。假設輸入數組的任意兩個數字都不相等。
等價于
輸入一個整數數組，判斷該數組是不是有序遞增的。假設輸入數組的任意兩個數字都不相等。

字符的組合

本題為《劍指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

解答

auto groupOfChars(string s, int strLength) -> void{
    //依次求長度從1~字符串長度的所有組合
    for(int i = 1; i <= strLength; ++i){
        groups(s, strLength, i, "");
    }
}

//參數分別為：字符串，字符串長度，組合長度，頭字符串（累計存儲的第一個字符）
auto groups(string s, int strLength, int groupLength, string headStr) -> void{

    //如果字符串長度等于組合長度，則輸出字符串（頭字符串放前面）
    if(strLength == groupLength){
        cout << headStr << s << endl;
        return;
    }

    //如果組合長度為1，則依次輸出字符串中的單個字符（頭字符串放前面）
    if(groupLength == 1){
        for(int i = 0; i < strLength; ++i){
            cout << headStr << s[i] << endl;
        }
        return;
    }

    //將除第一個字符外的字符串截取出來
    string sub(s.begin() + 1, s.end());
    //不包含第一個字符的情況，頭字符串不做改動，依舊為之前遞歸下來的頭字符串。
    groups(sub, strLength - 1, groupLength, headStr);
    //包含第一個字符的情況，把字符串中的第一個字符截取出來，加到之前遞歸下來的頭字符串之后
    headStr += string(s.begin(),s.begin()+1);
    groups(sub, strLength - 1, groupLength - 1, headStr);
}

正方體的頂點

本題為《劍指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個數字的排列，再依次遞歸下去。

解法

//設置一個全局變量來存儲是否存在組合
bool flag = false;
//接收維度固定為8的數組，這樣如果傳入數組元素不足8個會自動補0，也可以手動傳入數組長度，更便于拓展
auto func(int numbers[8]) -> bool{
    allArray(numbers, 0);
    return flag;
}
auto canBeCube(int numbers[8]) -> bool{
    bool flag1 = numbers[0]+numbers[1]+numbers[2]+numbers[3] == numbers[4]+numbers[5]+numbers[6]+numbers[7];
    bool flag2 = numbers[0]+numbers[2]+numbers[4]+numbers[6] == numbers[1]+numbers[3]+numbers[5]+numbers[7];
    bool flag3 = numbers[0]+numbers[1]+numbers[4]+numbers[5] == numbers[2]+numbers[3]+numbers[6]+numbers[7];

    //只要有任意一個排列符合要求就將全局變量flag設置為真
    if(flag1 && flag2 && flag3){
        flag = true;
    }
    return (flag1 && flag2 && flag3);
}


auto allArray(int numbers[8], int begin) -> void{
    //本算法將所有符合要求的排列都求出來了，題目要求只需要判定是否存在符合要求的排列，如果只是完成題目要求可以在這里加上，如果全局變量flag為真，直接返回。
    //達到數組末尾，判定當前排列是否符合條件，符合的話就打印出來。
    if(begin >= 8){
        if(!canBeCube(numbers)) return;
        for(int i = 0; i < 8; ++i){
            cout << numbers[i] << " ";
        }
        cout << endl;
        return;
    }

    //依次將數組中的元素與首元素進行交換，完成遞歸后，再交換回來
    for(int i = begin;i < 8; ++i){
        int tmp = numbers[i];
        numbers[i] = numbers[begin];
        numbers[begin] = tmp;

        allArray(numbers, begin + 1);

        tmp = numbers[i];
        numbers[i] = numbers[begin];
        numbers[begin] = tmp;
    }
}

8個皇后

本題為《劍指Offer》“面試題28：字符串的排列”一節中的“相關題目”。

在8 X 8的國際象棋上擺放8個皇后，使其不能相互攻擊，即任意兩個皇后不得處在同一行、同一列或者同一對角線上。請問總共有多少種符合條件的擺法。

分析

可以定義一個含有8個數字0~7的數組，數組下標表示行號，數組元素的值表示列號，這樣任意順序的數組都可以符合皇后不能擺在同一行同一列的要求。再把所有的排列求出來，計算其中符合不在同一對角線的要求的排列數。

解法

本題大多數代碼都與上題一致，只有全局變量和判定函數不同。具體求出所有排列的算法可以參照上題。

//用于保存符合條件排列個數的全局變量
int sum = 0;
auto canPlace(int numbers[8]) -> bool{
    for(int i = 0; i < 8; ++i){
        for(int j = 0; j < 8; ++j){
            //如果是同一個棋子，則跳過
            if(i == j){
                continue;
            }
            //如果有在同一對角線上的棋子，直接返回false
            if(i - j ==  numbers[i] - numbers[j] || j - i == numbers[i] - numbers[j])
            {
                return false;
            }
        }
    }
    //排列數加1
    ++sum;
    return true;
}