【剑指offer】解题思路27-38

文章目录

总结备忘
第四章解决面试题的思路

总结备忘

第一遍没做出来（或者做的时候比较吃力的题目）：

29，顺时针打印矩阵，按照自己的想法没写下去，但是应该也是可行的，回头自己尝试写完。

32,扩展2，之字形打印二叉树。没有想到用两个栈，而是自己添加flag变量，通过设置flag变量的true或False来表示奇偶层。这个想法的问题在于：当前层还没打印完的时候，子节点就已经压进栈中了。

33，二叉搜索树的后序遍历（反推），拿到题之后全没思路。

34，二叉树中和为某一值的路径（递归），自己没写出来。回头需要重点加强。

36题，拿到题之后完全不会，后来才发现其实就是中序遍历的一个应用而已，还是要加强练习。

37，二叉树的反序列化（即二叉树重构），给定前序，中序，后序遍历的字符串吗，重构二叉树，这块还需加强。

38，全排列，全组合。递归解法，需要掌握。

二刷记录：

33，小坑没跳过去（判断右子树的所有值都要大于root）

36，

第四章解决面试题的思路

4.2 画图让抽象问题形象化

面试题27：二叉树的镜像(递归/循环)

【题目描述】：

输入一颗二叉树，输出它的镜像。例如，将左图所示二叉树进行镜像处理，输出为右图。

【解题思路】：

思路比较简单，就是每一个节点的左右节点互换即可（叶节点除外，因为叶节点没有左右子节点）。可以使用递归和循环的方式来实现。

递归：对于根节点，交换其左右节点；然后分别对其左右子节点递归调用函数。
循环：用一个队列保存节点，只要队列不为空就一直循环，每次从队列头部取出一个节点，对于当前节点，交换其左右节点，并将其右节点和左节点依次加入队列。如果是叶节点(没有左右节点)，直接continue即可。

面试题28：对称的二叉树(递归)

【题目描述】：

判断一棵二叉树是不是对称的。如果一颗二叉树和它的镜像一样，那么它是对称的。

【解题思路】：

类似上图这样的称为对称的二叉树，对于同一层的两个节点（比如B和C），需要比较的是B的左孩子和C的右孩子，B的左孙子和C的右孙子，依次递归，但是根节点只有一个，如何处理呢？答案很简单，将根节点“分裂开”即可，这样根节点也就可以一并送入递归部分处理了。

——–2019.7.7 二刷———

对于根节点，比较左右孩子的值是否相等；如果相等，比较左孩子的左孩子和右孩子的右孩子（对称的）。

特殊用例：

二叉树为空
二叉树只有一个节点
二叉树所有节点值都相同。

面试题29：顺时针打印矩阵(重要)

【题目描述】：

输入一个矩阵，按照从外向里，顺时针打印矩阵，如下图，打印出1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10

在这里插入图片描述

解题关键：一圈一圈打印，每圈的起点是有规律可循的，都是对角线上的(start, start)点，而且对于n

n矩阵，对于rows

cols的矩阵，只需循环cols > startX × 2并且 rows > startY × 2次即可。

打印一圈需要经过四步：从左到右，从上到下，从右到左，从下到上。其中：

从左到右（第一步）：不需要任何条件，只要矩阵不为空，肯定要经过这步的。
从上到下（第二步）：前提条件，要求至少两行
从右到左（第三步）：前提条件，要求至少两行两列
从下到上（第四步）：前提条件，要求至少三行两列。

有了上述的分析，其实就很好写了，对于特定尺寸的矩阵，先判断需要循环几轮（走几圈），然后每圈按照以上四步打印即可。

4.3 举例让抽象问题具体化

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

题目要求：定义栈的数据结构，使其能够在O(1)的时间内得到栈的最小元素。

解法思路：在push和pop函数的时候需要修改一下，额外定义一个辅助栈，用来存栈里面的最小元素，push和pop栈顶元素的时候，辅助栈也要进行相应的push和pop操作。

面试题31：栈的压入，弹出栈列

题目要求：输入入栈序列和出栈序列，判断该出栈序列是不是该入栈序列可能的弹出顺序。

【判断一个序列是不是栈的弹出序列】

如果下一个弹出从数字刚好是栈顶数字，那么直接弹出；如果下一个弹出的数字不在栈顶，则把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止；如果所有数字都压入栈后仍没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

注意一个小细节：在比较的时候，不要手误写成类似
if stack.pop() == pop_list.pop()
的代码，比较完一轮之后，啥都没干列表就少元素了。。。检查了半天才发现emmm。只有在弹出的时候才能用pop。

面试题32：从上到下打印二叉树

二叉树的层序遍历。借助队列实现。

扩展0：广度优先遍历有向图

同样可以基于队列实现，树是图的退化形式，层序遍历二叉树，本质上来说就是广度优先遍历二叉树。

扩展1：分行从上到下打印二叉树

关键点：不能直接打印一串，还要对节点进行分层

解决方法：需要额外设置两个变量，一个是当前层还有几个节点等待打印，一个是下一层有几个节点。

扩展2：之字形打印二叉树(重要)

关键点：需要维护两个栈，在打印一个栈里的节点时，将它的子节点保存到另一个栈中，当一层所有节点都打印完毕时，交换着两个栈，并继续打印下一层。

面试题33：二叉搜索树的后序遍历(重要)

题目要求：输入一个数组，判断该数组是不是二查搜索树的后序遍历结果，返回True或False。

回顾：二叉搜索树，是一个二叉树，且满足左节点 < 父节点 < 右节点。

二叉树的后序遍历序列为：[5,7,6,9,11,10,8]

【二叉树后序遍历序列的规律】

最后一个数字是根节点的值，数组中前面的数字可以分为两部分，一部分是左子树节点的值，他们都比根节点的值小，另一部分是右子树节点的值，他们都比根节点的值大。

知道了上述规律，可以使用

递归

的方法实现。

【Attention】：本题需要特别注意的点是，每次递归左右子树之前，必须要保证左子树的所有数字都比root小，右子树的所有数字都比root大，否则没必要递归，直接返回False.

扩展0：二叉搜索树的前序遍历

也是同样的思路，只是前序遍历序列中，第一个数字是根节点的值。

面试题34：二叉树中和为某一值的路径(重要)

题目要求：输入一个二叉树和一个整数，打印出二叉树中节点值的和为该整数的所有路径（从根节点到叶节点）。

如图，给定二叉树和整数22，返回两条路径， [10,5,7]和[10,12]

这题其实是二叉树的深度优先遍历，在树的前序、中序、后序3中遍历方式中，只有**前序遍历是首先访问根节点的。**用递归的方式来解。

分析

看这里

，代码参考

看这里

。

4.4 分解让复杂问题简单化

面试题35：复杂链表的复制(掌握方法三的思路)

（

https://www.cnblogs.com/AndyJee/p/4654545.html

）

【方法1：（时间复杂度：O(N^2)）】

分两步实现：

复制原始链表上的每一个结点，并通过pNext连接起来；
然后再设置每个结点的pSibling指针。

缺点：假设原始链表中某个结点N的pSibling指针指向结点S,那么就需要从头到尾遍历查找结点S，如果从原始链表的头指针开始，经过m步之后达到结点S，那么在复制链表中的结点N’的pSibling指针指向的结点也是距离复制链表s步的结点。通过这种办法就可以为复制链表上的每个结点设置pSibling指针。

【方法2：(时间复杂度：O(N)，空间复杂度O(N))】

方法1是通过链表查找来得到pSibling指针所指向的结点，实际上我们可以通过空间换取时间，将原始链表和复制链表的结点通过哈希表对应起来，这样查找的时间就从O(N)变为O(1)。具体如下：

复制原始链表上的每个结点N创建N’，然后把这些创建出来的结点用pNext连接起来。同时把<N,N’>的配对信息方法一个哈希表中；然后设置复制链表中的每个结点的pSibling指针，如果原始链表中结点N的pSibling指向结点S，那么在复制链表中，对应的N’应该指向S’。

【方法3：

在不使用辅助空间的情况下实现O(N)的时间效率。

】（重要，掌握）

先遍历链表，复制每个节点，clone的节点紧接在原节点后面,得到图示的一个交叉链表，复杂度O（n）。
设置复制出来的结点的pSibling。将原来的pSibling线复制到clone的节点上，此过程遍历一次就可以完成，复杂度O（n）。
把长链表拆分成两个链表，

把奇数位置的结点用pNext连接起来的就是原始链表，把偶数位置的结点通过pNext连接起来的就是复制链表。

此过程复杂度O(n).

面试题36：二叉搜索树与双向链表(中序遍历)(重要)

题目要求：给定二叉搜索树，将该树转化为排序的双向链表，要求不能创建任何新的节点，只能调整树中节点指针的指向。

在这里插入图片描述

这个链接写的非常好

https://blog.csdn.net/u010005281/article/details/79657259

本题是二叉树中序遍历的一个应用，先中序遍历到最左侧的节点（即最小的元素对应的节点），然后将该节点设为双向链表的尾节点，在中序遍历的过程中，不断在其后添加新的节点，设置双向指针，并将尾节点后移，当遍历一轮后，双向链表即可生成。代码主要修改的是中序遍历的主体部分。

面试题37：序列化二叉树(二叉树遍历&二叉树重构)

题目要求：请实现两个函数，分别用来序列化和反序列化二叉树。

【二叉树的序列化】：把二叉树按照某种遍历方式（可以前序，中序，后序）的结果以某种格式保存为字符串，用特殊节点表示空节点

【二叉树的序列化】：序列化的反过程，利用字符串，重构二叉树。

这里写的是前序遍历的序列及反序列化，序列化比较简单，重点是反序列化，相当于重建二叉树。需要加强。

参考这里

面试题38：字符串的排列(全排列,递归)(重要)

题目要求：输入字符串，打印该字符串中字符的所有排列。

难点在于递归的实现，可以参考这篇博客，图文分析很详细

https://blog.csdn.net/u010591976/article/details/82048582

在这里插入图片描述

若含有重复字符，则要对全排列进行去重处理

https://blog.csdn.net/fuxuemingzhu/article/details/79513101

扩展：全组合(递归)(重要)

其实和全排列类似，也是用递归的方法实现，区别在于两点：

递归时传入的string字符串，由于是组合问题，所以ab和ba是一样的，没必要每次循环都传所有字符串进行，当首字符是a的时候，已经遍历了这种情况，因此，当首字符是b的时候，就只需要考虑和后面的字符之间的可能组合了。当遍历到最后一个字符时，只需要输出它本身即可。
全排列是要走到最后一步，才能输出完整的路径。但是对于全组合问题，需要每走一步打印一步，走到最后一步意味着终止。

注意下图的关键点：任何一个路径，如果一旦到达最后一个字符（d），就意味着该路径的终止。