遍历：前中后序，宽度优先。
二叉树的特例：二叉搜索树、堆（最大堆和最小堆，用于找最值）、红黑树（c++ STL中的很多数据结果就是基于这实现的）；
题7-重建二叉树：递归，设置四个位点；
class Linuxidc {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.size()!=vin.size()||vin.size()==0) return nullptr;
return Construct(0,pre.size()-1,0,vin.size()-1,pre,vin);
}
TreeNode* Construct(int prestart,int preend,int vinstart,int vinend,const vector<int> &pre,const vector<int> &vin){
if(prestart>preend) return nullptr;
TreeNode* root=new TreeNode(pre[prestart]);
for(int i=vinstart;i<=vinend;i++)
if(pre[prestart]==vin[i]){
root->left=Construct(prestart+1,prestart+i-vinstart,vinstart,i-1,pre,vin);
root->right=Construct(prestart+i-vinstart+1,preend,i+1,vinend,pre,vin);
break;
}
return root;
}
};
题8-二叉树的下一个节点
class Linuxidc {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode==nullptr) return nullptr;
if(pNode->right!=nullptr){
pNode=pNode->right;
while(pNode->left!=nullptr){
pNode=pNode->left;
}
return pNode;
}
else{
if(pNode->next==nullptr)
return nullptr;
else{
if(pNode==pNode->next->left)
return pNode->next;
else{
while(pNode->next!=nullptr){
if(pNode==pNode->next->left)
return pNode->next;
pNode=pNode->next;
}
return nullptr;
}
}
}
}
};
2.3.5 栈和队列
题9-两个栈实现队列：一个用于插入，一个用于删除，增加判空操作，每次插入/删除操作后只有一个栈是有数据的；
2.4 算法和数据结构
递归/循环，排序/查找，搜索路径（回溯法），最优解（动态规划），贪心，位运算（与、或、异或、左右移）
2.4.1 递归和循环
如果面试官没有要求，多采用递归；递归存在时间效率和调用栈溢出的问题；
题10-斐波那契数列：递归效率低，采用循环O（n），也可以用到数学公式用递归O（logn），青蛙跳和格子都是这个问题；
2.4.2 查找和排序
顺序查找、二分、哈希表查找、二叉排序树
交换使用swap函数，使用随机数配合递归来进行快排；
面试官的交流：要问排序的是什么数据、数据量，能用多少辅助空间？明确场景
题11-旋转数组的最小数字：O（n）到O（logn），使用二分，但是要有特殊处理，例如如果两个位点元素相等，则内部的应该进行顺序查找；
class Linuxidc {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size()==0) return 0;
int low=0,high=rotateArray.size()-1,mid=(low+high)/2;
if(rotateArray[low]<rotateArray[high]) return rotateArray[low];
if(high<2) return rotateArray[high];
while(low!=high-1){
if(rotateArray[low]<rotateArray[high]) return rotateArray[low];
if(rotateArray[low]==rotateArray[mid]&&rotateArray[mid]==rotateArray[high]){
int min=rotateArray[low];
for(int i=low+1;i<=high;i++)
if(min>rotateArray[i])
min=rotateArray[i];
return min;
}
if(rotateArray[low]>rotateArray[mid]){
//low=low+1;
high=mid;
mid=(low+high)/2;
}
if(rotateArray[high]<rotateArray[mid]){
low=mid;
mid=(low+high)/2;
}
}
return rotateArray[low+1];
}
};
2.4.3 回溯法
适合用递归实现，其实也可以用堆栈。
题13-机器人的运动规划：本来觉得两轮遍历就可以找到不可以到达的格子，后来发现是不对的，所以还是用了回溯去找