[剑指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;
}