《剑指Offer》第4章笔记 解题的思路 P1

写代码之前理思路，举例子和画图都是很好的办法。

1 面试官谈面试思路

一些大佬说的话。

咕咕待更。

2 画图让抽象问题形象化

画图是在面试过程中应聘者用来帮助自己分析、推理的常用手段。很多面试题很抽象，不容易找到解决办法。这时不妨画出一些与题目相关的图形，借以辅助自己观察和思考。图形能使抽象的问题具体化、形象化，说不定通过几幅图形就能找到规律，从而找到问题的解决方案。

有不少与数据结构相关的问题，比如二叉树、二维数组、链表等问题，都可以采用画图的方法来分析。

面试的时候，需要向面试官解释自己的思路，对于复杂的问题，应聘者光用言语未必能够说清楚，这个时候也可以画出几幅图形，一边看着图形一边讲解。

面试题27-29

面试题27：二叉树的镜像。

完成一个函数，输入一棵二叉树，函数输出它的镜像。二叉树节点定义：

struct node {
    int value;
    node* pleft;
    node* pright;
};

画出一个镜像的二叉树后，观察可以发现只要简单地从上到下地交换每个节点的左右节点即可。

完整实现代码：

#include <iostream>

struct node {
    int value;
    node* pleft;
    node* pright;
};

node* init_node(int value) { ... }
node* init_tree() { ... }
void in_order_print(node* pnode) { ... }

void mirror_recursively(node* pnode) {
    if(pnode == nullptr) {
        return;
    }
    node* temp = pnode->pleft;
    pnode->pleft = pnode->pright;
    pnode->pright = temp;
    mirror_recursively(pnode->pleft);
    mirror_recursively(pnode->pright);
}

int main() {
    node* tree = init_tree();
    in_order_print(tree);
    printf("\n");

    mirror_recursively(tree);

    in_order_print(tree);
    printf("\n");
    return 0;
}

如果不使用递归，而是使用循环实现的话，可以考虑用一个队列来实现点的从上到下遍历的模拟，每访问一个节点，交换完毕后，将左右子节点加入到队列中，每次从队列中取出一个节点进行交换子节点操作，直到所有节点被处理完毕。

---

面试题28：对称的二叉树。

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

完整实现代码：

#include <iostream>

struct node {
    int value;
    node* pleft;
    node* pright;
};

node* init_node(int value) { ... }
node* init_tree() { ... }

bool is_symmetrical(node* pnode1, node* pnode2) {
    if(pnode1 == nullptr && pnode2 == nullptr) {
        return true;
    }
    if(pnode1 == nullptr || pnode2 == nullptr) {
        return false;
    }
    if(pnode1->value == pnode2->value) {
        bool lr_result = is_symmetrical(pnode1->pleft, pnode2->pright);
        bool rl_result = is_symmetrical(pnode1->pright, pnode2->pleft);
        return lr_result && rl_result;
    } else {
        return false;
    }
}

bool is_symmetrical(node* proot) {
    if(proot == nullptr) {
        return true;
    }
    return is_symmetrical(proot->pleft, proot->pright);
    // 或者可以写为 虽然会多一倍计算过程 但代码精简到一行，有点抽象
    // return is_symmetrical(proot, proot);
}

int main() {
    node* tree = init_tree();
    if(is_symmetrical(tree)) {
        printf("Tree is symmetrical.\n");
    } else {
        printf("Tree is not symmetrical.\n");
    }
    return 0;
}

---

面试题29：顺时针打印矩阵。

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。例如，如果输入如下矩阵，则依次打印数字1、2、3、4、8、12、16、15、15、13、9、5、6、7、11、10。

完整实现代码：

#include <iostream>

void print_matrix_clockwise(int** matrix, int rows, int cols) {
    if(matrix == nullptr || rows <= 0 || cols <= 0) {
        return;
    }
    int up = 0, bottom = rows-1, left = 0, right = cols-1;
    int i, j;
    while(up < bottom && left < right) {
        // 从左到右打印
        i = up;
        for(j = left; j <= right; j++) {
            printf("%d ", matrix[i][j]);
        }
        up++;
        // 从上到下打印
        j = right;
        for(i = up; i <= bottom; i++) {
            printf("%d ", matrix[i][j]);
        }
        right--;
        // 从右到左打印
        i = bottom;
        for(j = right; j >= left; j--) {
            printf("%d ", matrix[i][j]);
        }
        bottom--;
        // 从下到上打印
        j = left;
        for(i = bottom; i >= up; i--) {
            printf("%d ", matrix[i][j]);
        }
        left++;
    }
    // 当列数或行数是奇数时
    // 会出现多余一列或者一行的情况
    if(rows & 0x1 == 1 || cols & 0x1 == 1) {
        // 最后一列
        if(up < bottom) {
            j = left;
            for(i = up; i <= bottom; i++) {
                printf("%d ", matrix[i][j]);
            }
        }
        // 最后一行
        if(left < right) {
            i = up;
            for(j = left; j <= right; j++) {
                printf("%d ", matrix[i][j]);
            }
        }
    }
}

int main() {
    int rows = 4, cols = 4;
    int** matrix = new int*[rows];
    for(int i = 0; i < rows; i++) {
        matrix[i] = new int[cols];
        for(int j = 0; j < cols; j++) {
            matrix[i][j] = i * 4 + j + 1;
        }
    }
    print_matrix_clockwise((int**)matrix, rows, cols);
    return 0;
}

在实现完整代码的时候，其中需要注意的一个问题是，二维数组的传参问题，如果想像题目一样传指针的方式传参，就需要在主函数使用动态数组的申请方式，用普通的声明方式int matrix[][]再强转(int**)matrix虽说可以传入到函数中，但访问数组会发生错误（原因暂时没有去细究了，应该和内存段的访问相关）。

3 举例让抽象问题具体化

包含面试题30-34。

请到《第4章笔记 高质量代码 P2》阅读这部分内容。

4 分解让复杂问题简单化

包含面试题35-38。

请到《第4章笔记 高质量代码 P3》阅读这部分内容。