第四章：解决面试题的思路

面试题19：二叉树的镜像

二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5

其实整个过程，画图后很容易发现，只要交换根节点的左右指针即可。

void Mirror(TreeNode *pRoot) { if(!pRoot){ return ; } TreeNode* t=pRoot->left; pRoot->left=pRoot->right; pRoot->right=t; Mirror(pRoot->left); Mirror(pRoot->right); }

面试题20：循环打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 思路：每次由左上角和右下角确定一个范围，打印该范围的外圈，分四个步骤打印。每个步骤从某个“角”，打印至下一个“角”前。

11124xx24xx24333

上图是最“优雅”的情况，写起来也最好看

void printMatWrong(const vector<vector<int> >& mat,int r1,int c1,int r2,int c2,vector<int>& res){ if(r2>=r1 && c2>=c1){ for(int c=c1;c<c2;++c) res.push_back(mat[r1][c]); for(int r=r1;r<r2;++r) res.push_back(mat[r][c2]); for(int c=c2;c>c1;--c) res.push_back(mat[r2][c]); for(int r=r2;r>r1;--r) res.push_back(mat[r][c1]); printMat(mat,r1+1,c1+1,r2-1,c2-1,res); } }

然而，这是错误的，因为当行数或列数等于1的时候，一定会出错。具体自行证明。 所以调整步骤，第1第3步打印一整行。

11114xx24xx23333 void printMat(const vector<vector<int> >& mat,int r1,int c1,int r2,int c2,vector<int>& res){ if(r2>=r1 && c2>=c1){ for(int c=c1;c<=c2;++c) res.push_back(mat[r1][c]); for(int r=r1+1;r<r2;++r) res.push_back(mat[r][c2]); if(r2!=r1) for(int c=c2;c>=c1;--c) res.push_back(mat[r2][c]); if(c1!=c2) for(int r=r2-1;r>r1;--r) res.push_back(mat[r][c1]); printMat(mat,r1+1,c1+1,r2-1,c2-1,res); } }

注意，在程序后半部分，对r1和r2进行了相等判断；因为如果两者相等，则会重复打印。c1和c2同理。

面试题21： 包含min函数的栈

设计栈，使得可以在常数时间返回最小值。

class Solution { public: void push(int value) { s1.push(value); if(s2.empty()||value<s2.top()){//短路求值 s2.push(value); }else{ s2.push(s2.top()); } } void pop() { s1.pop(); s2.pop(); } int top() { return s1.top(); } int min() { return s2.top(); } private: stack<int> s1,s2; };

其实说起来也容易，定义两个栈，数据栈单纯地压入弹出数据；MIN栈在数据栈压入数据的时候，同步压入数据，不过压入的是当前栈的最小值（新数据或旧栈顶）。栈顶永远是当前规模的栈内最小值。 例如：压入4 1 3: 压入4，MIN栈压入4，栈顶为4，是[4]的最小值 压入1，MIN栈压入1，栈顶为1，是[4 1]的最小值 压入3，MIN栈压入1，栈顶为1，是[4 1 3]的最小值。 栈弹出时，MIN栈同步弹出。 因为栈的压入和弹出是镜像的，所以压入或弹出到任何规模的时候，MIN栈顶永远是当前规模的最小值。

面试题22：栈的压入弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。 压入：1 2 3 4 5 弹出：4 5 3 2 1

bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int> st; int id=0; for(int i=0;i<popV.size();++i){ while(st.empty()||st.top()!=popV[i]){ st.push(pushV[id++]); if(id>pushV.size()){ return false; } } st.pop(); } if(st.empty()) return true; else return false; }

重点在于思路： 弹出的第一个数是4，则需从压入序列中，挨个压入数字直到压入4为止。如果序列压完了，还没找到4，就一定出错了。然后从栈弹出4，继续处理弹出序列的下一个数。 所有流程处理完后，栈应该是空的才对。

面试题23：从上向下打印二叉树

其实是一个广度优先的搜索问题，主要手段是队列。

vector<int> PrintFromTopToBottom(TreeNode* root) { vector<int> v; if(!root) return v; queue<TreeNode*> que; que.push(root); TreeNode* p; while(!que.empty()){ p=que.front(); que.pop(); v.push_back(p->val); if(p->left) que.push(p->left); if(p->right) que.push(p->right); } return v; }

面试题24：二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 后序意味着根元素最后访问，又因为根元素是左右子树的分界值，所以后序序列的最右值，一定可以把其他部分切为两部分，使得前部分均小于它，后部分均大于它。同理两部分均递归做判断。

bool OK(int* a,int left,int right){ //退出条件：数组规模为1或0 if(right-left<=1){ return true; } int mid=a[right]; int i; //找出前段数组的边界。 for(i=left;i<right;++i){ if(a[i]>mid) break; } //a[i]是第一个大于mid的数；或者i为right //前段数组必须满足判断 if(!OK(a,left,i-1)) return false; //后段数组必须不能出现小于mid的值 for(;i<right;++i){ if(a[i]<mid) return false; } //后段数组必须满足判断 if(!OK(a,i,right-1)) return false; return true; }

面试题25：二叉树中和为某一值的路径

这其实是搜索，搜索至叶子节点为止，每次搜索需要记录路径信息；每次搜索完成后，检查路径是否满足要求。

vector<vector<int> > res; void ser(TreeNode* p,vector<int>& v,int num){ v.push_back(p->val); if(!p->left && !p->right){ if(accumulate(v.begin(),v.end(),0)==num){ res.push_back(v); } v.pop_back(); return; }else{ if(p->left) ser(p->left,v,num); if(p->right) ser(p->right,v,num); v.pop_back(); } } vector<vector<int> > FindPath(TreeNode* root,int expectNumber) { vector<int>v; if(!root) return res; ser(root,v,expectNumber); return res; }

这是典型的回溯法深度优先搜索；有几点需要注意： 1. 一般来说，搜索终止条件有两种：要么是找到某节点，要么是搜索完所有路径。这里是搜索完所有路径。 2. 每次递归时，参数内有一个vector的引用，用来记录先前的历史路径，这是一个状态量。状态量每次退出函数时，要进行回溯，以恢复现场。另一个进行回溯的例子是递归全排列。 3. 每次搜索时，遇见叶子即终止。而非遇见空终止。每次迭代，当前存在孩子，才会迭代进入孩子。保证每次搜索不为空。如果为空的话，通常是不合理的。

关于深度优先和广度优先： 一般来说，广度优先搜索效率较高，且用途广泛，比如最短路径等。但是这里需要记录历史路径，深度优先使用起来更容易，递归时的vector的压入弹出，很符合路径记录和追溯的情形。 如果使用广度优先，通常需要在树的节点上记录该节点的路径，具体类似于迪杰斯提拉求图的最小路径一样，每个节点要记录路径长。 这两种方法，在迷宫问题时会继续描述。

面试题26：复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个rand指针指向任意一个节点），返回结果为复制后复杂链表的head。 思路很奇特： 1. 每个节点后链接一个它的拷贝； 2. 拷贝节点rand指针，指向源节点的rand节点的拷贝； 3. 剥离拷贝节点创建新链表

struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) {} }; RandomListNode* Clone(RandomListNode* pHead){ if(pHead==nullptr) return nullptr; //每个源节点后面加一个拷贝节点 RandomListNode* p=pHead; while(p){ RandomListNode* pnew=new RandomListNode(p->label); pnew->next=p->next; p->next=pnew; p=pnew->next; } //每个拷贝节点的rand指针，指向它源节点的rand节点的拷贝（除非为空） p=pHead; while(p){ if(p->random!=nullptr){ p->next->random=p->random->next; }else{ p->next->random=nullptr; } p=p->next->next; } //把拷贝节点剥离出来 RandomListNode* Hnode=new RandomListNode(0); RandomListNode* last=Hnode; p=pHead; while(p){ last->next=p->next; last=last->next; p->next=p->next->next; p=p->next; } last->next=nullptr; RandomListNode* h=Hnode->next; delete Hnode; return h; }

注意： 1. 因为每个源节点后一定有一个拷贝节点，所以遍历源节点，使得逻辑更清晰。 2. 无头链表在递归中容易处理，有头链表在循环中容易处理。这里是新建了一个头节点，暂时制造了一个有头链表，使得处理起来更容易。 扩展：按照两种类型来剥离一个链表。按照三种类型来剥离链表。如果无头，处理会极其麻烦。除非自造带头链表，或用递归。

面试题27：二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

void conv(TreeNode* p,TreeNode* &Left,TreeNode* &Right){ if(!p->left && !p->right){ Left=Right=p; return; } if(p->left){ TreeNode *L,*R; conv(p->left,L,R); p->left=R; R->right=p; Left=L; }else{ Left=p; } if(p->right){ TreeNode *L,*R; conv(p->right,L,R); p->right=L; L->left=p; Right=R; }else{ Right=p; } } TreeNode* Convert(TreeNode* pRootOfTree){ if(pRootOfTree==nullptr) return nullptr; TreeNode* Left,*Right; conv(pRootOfTree,Left,Right); return Left; }

我的解法和书本略有不同，函数conv对于某个二叉树，找到它的最左节点，和最右节点。如果根节点有左子树，则需要链接左子树的最右节点；如果根有右子树，需要链接右子树的最左节点。然后返回整个树的最左和最右节点。

面试题28：字符串的全排列

这种套路式的问题，理解起来很艰难。比如12345，第一个位置，先放1，然后后面4个位置全排列，就化简到了4个数的全排列。第一个位置放2,3,4,5，后面的分别全排列，即可。 函数有参数m，表示当前处理第m位。处理方式是把m位后面（包括自己）的位与其交换，然后递归排列后面的位置。注意不要漏掉自己，相当于未交换的原始排列，当然也算一种。 递归返回的时候，需要回溯，恢复现场，把交换过去的换回来。

void permu(string& str,int m,vector<string>& res){ if(m>=str.size()){ res.push_back(str); return; } for(int i=m;i<str.size();++i){ swap(str[i],str[m]); permu(str,m+1,res); swap(str[i],str[m]); } }

注意：str必须用引用，因为它记录了调用时的“状态”。改变了状态的时候，回溯时要改回来。 如果字符串中有重复的值，那么输出的结果一定有重复的。此时可以用set代替vector。 扩展：八皇后问题 因为八皇后不能在同一行或一列中，所以每一行都只有一个皇后，每一列都只有一个皇后。所以我们用1到8的全排列，表征每一行的皇后，分别在哪一列。然后对每种情况进行判断，看看是否有两个皇后，在一个斜线上。这个过程需要用两层的循环。判断斜线的条件是，下标的差（行差）绝对值等于值（列差）的差。