2.3.4 树

遍历：前中后序，宽度优先。

二叉树的特例：二叉搜索树、堆（最大堆和最小堆，用于找最值）、红黑树（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 查找和排序

顺序查找、二分、哈希表查找、二叉排序树