剑指offer读书笔记：第四章，解决面试题的思路01

短命女 2022-05-30 09:52 133阅读 0赞

![这里写图片描述][70]

# 问题01 二叉树的镜像–>反转二叉树 #

![这里写图片描述][70 1]

这个就是著名的反转二叉树问题

void exchangeBTree(BTRee *root)
    {
      BTRee *t;
      if(root)
         {
             t=root->rChild;
             root->rChild=root->lChild;
             root->lChild=t;
             exchangeBTree(root->lChild);
             exchangeBTree(root->rChild);
         }
    }

# 问题02 顺时针打印矩阵 #

![这里写图片描述][70 2]

一个简单的状态机。

public class Test20 {
        
        /**
         * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印每一个数字
         *
         * @param numbers 输入的二维数组，二维数组必须是N*M的，否则分出错
         */
        public static void printMatrixClockWisely(int[][] numbers) {
            // 输入的参数不能为空
            if (numbers == null) {
                return;
            }
            // 记录一圈（环）的开始位置的行
            int x = 0;
            // 记录一圈（环）的开始位置的列
            int y = 0;
            // 对每一圈（环）进行处理，
            // 行号最大是(numbers.length-1)/2
            // 列号最大是(numbers[0].length-1)/2
            while (x * 2 < numbers.length && y * 2 < numbers[0].length) {
                printMatrixInCircle(numbers, x, y);
                // 指向下一个要处理的的环的第一个位置
                x++;
                y++;
            }
        }
        public static void printMatrixInCircle(int[][] numbers, int x, int y) {
            // 数组的行数
            int rows = numbers.length;
            // 数组的列数
            int cols = numbers[0].length;
            // 输出环的上面一行，包括最中的那个数字
            for (int i = y; i <= cols - y - 1; i++) {
                System.out.print(numbers[x][i] + " ");
            }
            // 环的高度至少为2才会输出右边的一列
            // rows-x-1：表示的是环最下的那一行的行号
            if (rows - x - 1 > x) {
                // 因为右边那一列的最上面那一个已经被输出了，所以行呈从x+1开始，
                // 输出包括右边那列的最下面那个
                for (int i = x + 1; i <= rows - x - 1; i++) {
                    System.out.print(numbers[i][cols - y - 1] + " ");
                }
            }
            // 环的高度至少是2并且环的宽度至少是2才会输出下面那一行
            // cols-1-y：表示的是环最右那一列的列号
            if (rows - x - 1 > x && cols - 1 - y > y) {
                // 因为环的左下角的位置已经输出了，所以列号从cols-y-2开始
                for (int i = cols - y - 2; i >= y; i--) {
                    System.out.print(numbers[rows - 1 - x][i] + " ");
                }
            }
            // 环的宽度至少是2并且环的高度至少是3才会输出最左边那一列
            // rows-x-1：表示的是环最下的那一行的行号
            if (cols - 1 - y > y && rows - 1 - x > x + 1) {
                // 因为最左边那一列的第一个和最后一个已经被输出了
                for (int i = rows - 1 - x - 1; i >= x + 1; i--) {
                    System.out.print(numbers[i][y] + " ");
                }
            }
        }

# 问题03 包含min函数的栈 #

![这里写图片描述][70 3]

我们可能想使用一个变量min来存放最小的元素。每次压入栈中一个元素的时候，如果新元素比这个变量min中保存的元素小，那么就将用新元素给min赋值，即更新min的值。但是，这样存在一个问题，那就是当当前最小的元素被弹出栈了，怎么得到栈中剩余元素的最小的元素呢？因此，可以借助一个辅助栈，用来存放每次栈操作时（包括入栈和出栈）栈中最小元素。

class Solution {
    public:
        stack<int> st, minSt;//st表示存储元素的栈，minSt保存每次栈操作时，保存栈中最小元素
        void push(int value)
         {
            st.push(value);
            {
       //如果栈minSt为空，将value入栈，value就是当前最小的元素
                minSt.push(value);
            }
            else
             {
       //如果栈minSt不为空，将value的值与minStrel栈的栈顶元素比较。因为minSt栈的栈顶元素此时为栈中所有元素的最小值
                if (value < minSt.top())
                    minSt.push(value);
                else 
                    minSt.push(minSt.top());
            }
            return;
        }
        void pop() 
        {
       //出栈时，需要对两个栈st和minSt同时操作
            if (!st.empty()) 
            {
                st.pop();
                minSt.pop();
            }
            return;
        }
        int top()
        {
            if (!st.empty())
                return st.top();
            return 0;
        }
        int min()
         {
            if (!minSt.empty()) 
                return minSt.top();
            return 0;
        }
    };

# 问题04 栈的压入、弹出序列 #

![这里写图片描述][70 4]

直观的想法就是模拟第一个序列的数字依次入栈，并按照第二个序列依次弹出，如果第一个序列全部入栈，并最后栈中元素都被弹出来，就说明第二个序列是该栈的弹出顺序。

*  建立一个辅助栈；
 *  将第一个序列的数字压入辅助栈；
 *  如果第二个序列的下一个弹出数字刚好是栈顶数字，则直接弹出，第二个序列弹出当前数字，辅助栈也弹出该数字；
 *  否则，就把第一个序列中尚未入栈的数字压入辅助栈，直到把第二个序列中下一个需要弹出的数字压入栈顶为止。
 *  如果第一个序列的所有数字都已经入栈了，仍然没有找到下一个弹出的数字，那么第二个序列不可能是一个弹出序列。  
    代码如下：

include <iostream>
    #include <stack>
    
    using namespace std;
    
    bool IsPopOrder(const int* push,const int* pop,int length){
        bool bPossible=false;
        if(push!=NULL && pop!=NULL && length>0){
            std::stack<int> stackData;
            int i=0;
            int j=0;
            while(j<length){
                while(stackData.empty() || stackData.top()!=pop[j]){
                    if(i>length-1)
                        break;
                    stackData.push(push[i]);
                    ++i;
                }
                if(stackData.top()!=pop[j])
                    break;
                stackData.pop();
                ++j;
            }
            if(stackData.empty() && j==length)
                bPossible=true;
        }
        return bPossible;
    }

# 问题05 从上往下打印二叉树 #

![这里写图片描述][70 5]

也即简单的BFS广度优先遍历的做法，不多说了

# 问题05 二叉搜索树的后序遍历序列 #

![这里写图片描述][70 6]

#include<cstdio>
    #include<vector>
    using namespace std;
    class Solution
    {
    public:
        bool VerifySquenceOfBST(vector<int> sequence)
        {
            int len=sequence.size();
            if(len<=0) 
                return false;
    
            vector<int> left, right;
            int root=sequence[len-1];
            int i=0;
            while(i<len-1)  // 处理left部分 
            {
                if(sequence[i]>root) 
                    break;
                left.push_back(sequence[i]);        
                i++;
            }
    
            int j=i; // 处理right部分，此时i为left部分最后一个结点的下标 
            while(j<len-1)
            {
                if(sequence[j]<root) 
                    return false;
                right.push_back(sequence[j]);
                j++;
            }   
            bool bleft=true; // 应初始化为true，left部分是BST序列，才能调用VerifySquenceOfBST() 
                if(i != 0) 
                    bleft=VerifySquenceOfBST(left); // i为left部分最后一个结点的下标 ，i!=0表示有左子树 
    
            bool bright=true;
            if(i != len-1) 
                bright=VerifySquenceOfBST(right);  // i!= len-1表示有右子树
    
            return (bleft && bright);
        }
    };

[70]: /images/20220530/9954de078c1f4f12ac32cc6fab1bdf7b.png
[70 1]: /images/20220530/a8c8599cb5a14776adf342936c7f8c78.png
[70 2]: /images/20220530/7fa4dbb6904a46f2849eec4d120ad69f.png
[70 3]: /images/20220530/80249c06a1634c19bdb8df72676f89c1.png
[70 4]: /images/20220530/d20a1c20ee014b44bdeff766a42557d7.png
[70 5]: /images/20220530/075561de17c64bf6ac830a342531ad5c.png
[70 6]: /images/20220530/f0554abb5ff84d20bd7db056eceeeea7.png