回复：记录我的转行之路

有大佬知道这个是什么问题吗

今天一晚上就整了几道二叉树的题，感觉自己好笨啊。一道二叉树的最近公共节点，用了两种做法，一种是思路是目标节点在当前节点左右子树返回当前节点，目标节点是当前节点则返回当前节点否则返回空。第二种是用容器保存从根节点到目标节点的路径，最深路径交点为解，找到路径的思路是从根开始前序遍历，将当前节点保存到容器中，如果当前节点是目标节点则返回真层层返回，否则继续递归左右子树，不在左右子树则从容器中删除该节点返回否。还有一道搜索二叉树转化为双向链表的题，利用中序遍历并迭代前节点。

今天大部分时间还是刷二叉树的题，首先是二叉树的三种遍历的非递归方式，主要是用一个容器存储节点，再用循环解决子问题。还有一道比较难的，用前序和中序遍历得到的值重构二叉树，思想是利用前序找根用中序找左右区间连结并递归。还学了一点map和set的使用，马上要学AVL树和红黑树了，期待

今天主要学习map内的成员函数使用，一个是构造需要pair类型，通常使用make-pair函数构造，要注意的有一个是insert的返回值是一个pair类型的对象，first是插入或未成功插入位置的迭代器，second是布尔值代表是否插入成功。另一个是【】操作符的重载使用，可用来查找、修改key对应的value值，如果没有改key值则插入，它的返回值是pair的second对应为key-value。今天还学了AVL树的一部分，用平衡因子的方法构建一颗AVL树，插入的同时修改路径上的平衡因子值，如果值为2/-2则旋转，今天只学习了左单旋和右单旋。明天继续学习AVL树

今天继续学习AVL树，学习了树的双旋，靠的还是两个单旋，难点主要是平衡因子的修改。理一下AVL树的插入：1.先和平衡树一样的插入操作。2.插入后修改平衡因子直到根节点或前一个节点平衡因子为零。3.遇到节点的平衡因子为+_2时根据前后两个节点的平衡因子旋转。4.有4种旋转，难点在于双旋后的平衡因子修改。修改有三种情况，最好画图理解。下面是今天晚上写的代码和双旋的画图。

今天开整红黑树，与AVL树类似都是在搜索二叉树基础上改进，红黑树通过节点的颜色与颜色规则控制整个树的高度差。插入的过程遵循颜色规则，主要看叔叔节点是否为红色，为红则不需要旋转，不存在或为黑色就要旋转，旋转后的颜色改变要符合规则，具体规则我画了个图，代码也放在下面，主要写了插入。写完调试了好久，结果是旋转的代码写错了

今天把昨天的红黑树加上迭代器封装成map和set，难点在于map和set如何共用一棵树的结构，对节点里存储的内容用模板参数表示，再提供一个仿函数提取节点的key值。这块感觉很绕，大量使用模板，明天还得消化消化

今天消化了下昨天的map和set今天学了哈希，通过哈希函数，今天学的除拿去留法将关键字一一映射到储存结构中，不同的关键字通过函数映射到同一位置时就发生了哈希冲突，今天学的解决办法是闭散列中的线性检测及二次线性检测，重难点在于扩容

明天工作要换工地项目了，学习时间不知道还能不和以前一样

两天没时间学习了，明天赶车去新项目领导把啥事都交给我处理了

今天复习前天学的哈希，写了一下线性检测的代码