剑指Offer(3) 知识点：二叉树、栈和队列、查找 **更新：此题解 markdown 源文件已放到 Github [https://github.com/bytetopia/offer-coding-interviews-python](https://github.com/bytetopia/offer-coding-interviews-python)，欢迎前去给个小星星鸭！**</p> <p>---</p> <p>知识点：二叉树、栈和队列、查找</p> <p># 二叉树</p> <p>## 知识点</p> <p>- 树的概念：分支节点、叶节点、度、深度……<br /> - 二叉树的定义，满二叉树，完全二叉树<br /> - 二叉树的五条性质<br /> - 二叉树的存储方式（二叉链表广泛采用）<br /> - 二叉树的遍历（前序、中序、后序）（递归、非递归），以及层次遍历（采用队列）</p> <p>## 题目：重建二叉树</p> <p>### 要求<br /> 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。</p> <p>### 思路<br /> 前序序列能确定根节点，用根节点，把中序划分为左右子树<br /> 基于递归的思路，重复上述步骤</p> <p>### 代码<br /> ```python<br /> # -*- coding:utf-8 -*-<br /> # class TreeNode:<br /> # def __init__(self, x):<br /> # self.val = x<br /> # self.left = None<br /> # self.right = None<br /> class Solution:<br /> # 返回构造的TreeNode根节点<br /> def reConstructBinaryTree(self, pre, tin):<br /> # 给定前序和中序，重建二叉树<br /> # 思路：前序结果可以确定树根，通过树根可以将中序切成左右两半<br /> if(len(pre)==0):<br /> return None<br /> root = TreeNode(pre[0])<br /> tin_root_index = tin.index(root.val)<br /> if tin_root_index > 0: # 有左子树<br /> new_tin = tin[0: tin_root_index]<br /> new_pre = pre[1: len(new_tin)+1]<br /> root.left = self.reConstructBinaryTree(new_pre, new_tin)<br /> if tin_root_index != len(tin) - 1: # 有右子树<br /> new_tin = tin[tin_root_index+1:]<br /> new_pre = pre[len(pre)-len(new_tin):]<br /> root.right = self.reConstructBinaryTree(new_pre, new_tin)<br /> return root<br /> ```</p> <p>这个题主要是清楚前序和中序的特点，理清思路以后，算准确切分的下标，递归实现就行。<br /> 下标可以写的更简洁一点：</p> <p>```python<br /> index = tin.index(root.val)<br /> if index > 0: # 有左子树<br /> root.left = self.reConstructBinaryTree(pre[1: index+1], tin[0: index])<br /> if index != len(tin) - 1: # 有右子树<br /> root.right = self.reConstructBinaryTree(pre[index+1: ], tin[index+1: ])<br /> return root<br /> ```</p> <p># 栈和队列</p> <p>## 题目：用两个栈模拟队列<br /> ### 要求<br /> 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。</p> <p>### 思路<br /> 一个栈处理push，新节点放入该栈，一个栈处理pop，初始为空<br /> 当需要pop时，如果pop栈不空，则直接出栈，如果空，则从push栈弹出全部内容放到pop栈，pop栈出栈一个</p> <p>### 代码<br /> ```python<br /> # -*- coding:utf-8 -*-<br /> class Solution:<br /> # 思路：<br /> # 一个栈处理push，新节点放入该栈，一个栈处理pop，初始为空<br /> # 当需要pop时，如果pop栈不空，则直接出栈，如果空，则从push栈弹出全部内容放到pop栈，pop栈出栈一个<br /> def __init__(self):<br /> self.push_stack = []<br /> self.pop_stack = []</p> <p> def push(self, node):<br /> self.push_stack.append(node)</p> <p> def pop(self):<br /> if len(self.pop_stack) == 0:<br /> if len(self.push_stack) == 0:<br /> print('Nothing to pop!')<br /> return None<br /> else:<br /> for i in range(len(self.push_stack)-1,-1,-1):<br /> self.pop_stack.append(self.push_stack[i])<br /> self.push_stack = []<br /> value = self.pop_stack[-1]<br /> self.pop_stack = self.pop_stack[0:-1]<br /> return value<br /> ```</p> <p>思路很简单，主要是实现的时候，下标不要写越界。</p> <p>> 今天看到一个题，说用两个栈（长度分别为m、n，m大于n）来模拟队列，最大容量是多少。答案是 2n+1， 可以参考 https://www.cnblogs.com/eniac12/p/4865158.html</p> <p>### 扩展<br /> 如果用两个队列来模拟栈呢？<br /> 初始两个队列都为空<br /> 元素a，b，c入栈，则将a，b，c先加入到q1中吧<br /> 此时要弹出c，则将ab依次出队，并加入到q2中，将c删除（弹出）<br /> 要弹出b，则将a出队，加入到q1中，将b删除<br /> 要入栈d，由于q1不空，则追加到q1后面<br /> 以此类推。</p> <p># 查找</p> <p>## 题目：旋转数组的最小数字</p> <p>### 要求</p> <p>把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。</p> <p>### 思路<br /> 很简单，从前往后扫，找到第一个比上一个元素小的元素，就说明是最小元素了。<br /> 【注意特例】整个数组未旋转</p> <p>### 代码<br /> ```python<br /> class Solution:<br /> def minNumberInRotateArray(self, rotateArray):<br /> # 思路<br /> # 数组应该为非递减，找到第一个比上一个元素小的位置，就是最小值<br /> if len(rotateArray) == 0:<br /> return 0<br /> for i in range(len(rotateArray)-1):<br /> if rotateArray[i+1] < rotateArray[i]:<br /> return rotateArray[i+1]<br /> # 都没找到<br /> return rotateArray[0]<br /> ```</p> <p>感觉写完一遍跑过美滋滋，然而这种方法的时间复杂度为O(n)。<br /> 鉴于旋转数组前后两半都是有序的，可以采用类似二分查找的方法，减少比较次数。</p> <p>### 思路2</p> <p>整个数组由两个递增有序子数组构成。</p> <p></p> <p>两个指针分别指向首尾，按照旋转的规则，第一个元素应当大于或者等于最后一个元素（如果小于，说明数组未做旋转，第一个元素就是最小的）。</p> <p>找mid中间元素，如果mid属于前一半，则它应该大于或等于head，那么此时可以将head移动到mid处，head仍属于前一个数组，目标位于首尾之间；如果mid属于后一半，则它应该小于或等于rear，此时可将rear移动到mid，rear仍属于后一半，目标位于首尾之间。</p> <p>这种移动方式，head始终属于前一个数组，rear始终属于后一个数组，当hear和rear相邻的时候，说明到达了交界处，rear指向目标。</p> <p>### 代码2<br /> ```python<br /> def minNumberInRotateArray(self, arr):</p> <p> if len(arr) == 0:<br /> return 0<br /> head = 0<br /> rear = len(arr) - 1<br /> if arr[head] < arr[rear]: # 说明未旋转<br /> return arr[head]<br /> while(head != rear - 1): # 首尾未相遇，没找到目标<br /> mid = (head + rear) // 2<br /> # 【1】<br /> if arr[mid] >= arr[head]:<br /> head = mid<br /> continue<br /> if arr[mid] <= arr[rear]:<br /> rear = mid<br /> continue<br /> # 由于走到这一步，head值一定是大于等于rear的，因此除非三个值相等，不会出现mid同时满足大于等于head且小于等于rear的情况。<br /> return arr[rear]</p> <p>```</p> <p>### 补充</p> <p>前面代码中，如果头比尾小，说明未旋转，如果头大于等于尾，则进行mid的判断，此时head值一定是大于等于rear的，因此除非三个值相等，不会出现mid同时满足大于等于head且小于等于rear的情况，while中的两个if只能满足一个，写的没问题。</p> <p>但有一个特例没有考虑到。当head、mid、rear的值都相同时，按照代码，认为mid处仍然属于前一半，先把head移动到了mid处。但这样是对的吗？</p> <p></p> <p>上图两种情况，三个值相同，但可能是mid属于前一半，也可能mid属于后一半……上述方法就失效了，只能采用顺序查找的方法。</p> <p>所以在代码中【1】处，应当加一个判断，如果三者相等，则转到顺序扫描方法进行操作。</p> <p>**虽然这个题的顺序查找方法很简单，但要想多换种方法，提高一下效率，还是挺不容易的hhh** 赞微海报分享
近期评论