剑指offer之重建二叉树、用两个栈实现队列、旋转数组的最小数字
重建二叉树
题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
示例
输入
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值
{1,2,5,3,4,6,7}
方法：递归算法
二叉树的遍历知识：
二叉树的前序遍历：根->左->右
二叉树的中序遍历：左->根->右
二叉树的后序遍历：左->右->根
建立树的相关步骤：
struct TreeNode{
int vall;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};
//建树伪代码
TreeNode* build(1...){
if (2...) return nullptr;
TreeNode *root = new TreeNode(3...);
root->left = build(4...); //递归建立左子树
rott->right = build(5...); //递归建立右子树
return root;
}
通过记住建树伪代码中的1到5步，就可以建立一颗二叉树。那么1到5分别要填入什么呢？
假设：1. 数组vector 中的元素为树中的节点。
- 如果数组为空，则返回nullptr
- 新创建一个根结点的值
- 左子树的数组元素
- 右子树的数组元素
本段递归代码的理解就是，不断的创建二叉树中的根节点。因为二叉树中的左右子树节点也可以视为新树的根节点，所以不断的递归调用创建根节点，就可以创建一颗二叉树。具体化的步骤代码：
// 假设元素在数组v中，并且头结点的下标为 root_index, first < root_index < last,
// 这里只是会的容易讲解
TreeNode* build(int first, int last) {
if (first > last) return nullptr;
TreeNode *root = new TreeNode(v[root_index]);
root->left = build(first, root_index - 1);
root->right = build(root_index + 1, last);
return root;
}
那么这个root_index哪里来？根据先验知识了解到树的前序遍历数组的第一个元素便为二叉树的根节点，而树的中序遍历数组在根节点元素的左边的所有元素是左子树的序列，在右边的所有元素是右子树的序列。
以本题例子为例：
前序遍历序列： {1,2,4,7,3,5,6,8}
中序遍历序列： {4,7,2,1,5,3,8,6}
第一步：根结点为1
第二步：根结点在中序遍历序列中下标为3的位置，那么[0…2]就为左子树，[4…7]就为右子树
只不过现在build()参数中为2个数组，道理一样，维护2个数组的下标就行了。
那么现在这道题就可以解决了。
class Solution{
public:
TreeNode* reBuild(vector<int>& pre, int pre_left, int pre_right, vector<int>& vin, int vin_left, int vin_right){//1. 需要建立树的数组
if(pre_left < pre_right) return nullptr; //2. 数组判空
TreeNode* root = new TreeNode(pre[pre_left]); //3. 创建根节点
for(int i = 0; i <= vin_right; ++i){
if(vin[i] == pre[pre_left]){ // 找到中序遍历中的root_index
root->left = reBuild(pre, pre_left+1, pre_left+i-vin_left, vin, vin_left, i-1);//4. 左子树
root->right = reBuild(pre, pre_left+i-vin_left+1, pre_right, vin, i+1, vin_right);//5. 右子树
}
}
return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin){
return reBuild(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
}
}
其中递归左子树中，前序遍历的结尾为：pre_left + root_index - vin_left 的解释：
root_index - vin_left为根结点左边有几个元素
pre_left + root_index - vin_left 为从pre_left开始往后推这么多元素便是前序遍历的左子树序列。
用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
先验知识
- 入栈的元素是先进后出；
- 入队的元素是先进先出。
因此使用两个栈就可以实现一个队列操作，先将元素压入stack1，再将元素出栈，将出栈元素依次入stack2，最后将元素出栈，便实现了队列效果。
方法思路
push操作就只作用在stack1上，pop操作要分一下类：当stack2为空时，就将stack1中的元素转移到stack2中，然后对stack2进行pop操作；当stack2不为空时，直接pop
class Solution{
public:
void push(int node){
stack1.push(node);
}
int pop(){
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
stack1.pop;
}
}
int res = stack2.pop();
stack2.pop();
return res;
}
private:
stack<int> stack1;
stack<int> stack2;
}
旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
示例
输入
[3,4,5,1,2]
返回值
1
对于这种有序或部分有序的数组中查找某个元素，一般考虑使用二分法；或者说如果能够明确二分后，能够清楚的判断答案位于二分的某一侧，就可以使用二分法。
这种二分查找难就难在，arr[mid]跟谁比。我们的目的是：当进行一次比较时，一定能够确定答案在mid的某一侧。一次比较为 arr[mid]跟谁比的问题。一般的比较原则有：
- 如果有目标值target，那么直接让arr[mid]和target比较即可。
- 如果没有目标值，一般可以考虑端点
这里我们把target 看作是右端点，来进行分析，那就要分析以下三种情况，看是否可以达到上述的目标。
-
情况1， arr[mid] > target:
4, 5, 6, 1, 2, 3- arr[mid] 为 6， target为右端点 3，
arr[mid] > target，说明[first … mid] 都是 >= target 的，因为原始数组是非递减，所以可以确定答案为 [mid+1…last]区间，所以first = mid + 1
- arr[mid] 为 6， target为右端点 3，
-
情况2，arr[mid] < target:
5, 6, 1, 2, 3, 4- arr[mid]为1，target右端点为4，arr[mid] < target，说明答案肯定不在[mid+1…last]，但是arr[mid] 有可能是答案，或者答案在arr[mid]之前，所以答案在[first, mid]区间，所以
last = mid;
- arr[mid]为1，target右端点为4，arr[mid] < target，说明答案肯定不在[mid+1…last]，但是arr[mid] 有可能是答案，或者答案在arr[mid]之前，所以答案在[first, mid]区间，所以
-
情况3，arr[mid] == target:
- 如果是 1 0 1 1 1， arr[mid] = target = 1, 显然答案在左边
- 如果是 1 1 1 0 1, arr[mid] = target = 1, 显然答案在右边
所以这种情况，不能确定答案在左边还是右边，那么就让last = last - 1;慢慢缩少区间，同时也不会错过答案。
如图
代码：
class Solution{
public:
int minNumberInRotateArray(vector<int> rotateArray){
if(rotateArray.size() == 0) return 0;
int first = 0, last = rotateArray.size()-1;
while(first < last){ // 剩下最后一个元素，即为答案
int mid = floor((first + last)/2)
if (rotateArray[last] < rotateArray[mid]){ // 情况1
first = mid + 1;
}
else if(rotateArray[last] > rotateArray[mid]){//情况2
last = mid;
}
else{//情况3
--last;
}
}
return rotateArray[first];
}
}
复杂度分析
时间复杂度：二分，所以为O(longN)， 但是如果是[1, 1, 1, 1],会退化到O(n)
空间复杂度：没有开辟额外空间，为O(1)