大家好，我是阿秀。
前段时间，我把自己的剑指 offer 刷题笔记发在牛客上了（文末分享PDF版本的笔记）。其实在牛客网上已经有很多类似的专栏了，不过为什么我的专栏能上头条呢？
成功上首页
一个原因是可能长得帅，这我承认，但还是有其他原因的，且听我娓娓道来。
真实的原因
以下回答摘自本人在知乎上的回答：剑指offer，leetcode怎么刷？
言归正传，刷剑指 offer 的时候我刷了3遍，其中牛客网 2 遍，力扣平台 1 遍，自己的刷题笔记汇集了牛客和力扣的一些高赞高亮解法。
因为有些题目一样，但是平台后台设置的检测案例不一样，总的来说感觉还是力扣的后台案例更多一些更全面一些，想的更周到一些，建议去力扣刷剑指offer。
就拿剑指 offer 第 26 题来作例子吧。
NO26、二叉搜索树与双向链表 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能 调整树中结点指针的指向。
以下是我当时刷题时的笔记记录
第一种解法
第一天晚上我是写了下面第 1 种方法并且做了笔记的，当时还觉得不可思议，因为比自己想象中的要简单好多。
1、最笨的一种写法，这也是最容易理解的一种方法了
中序遍历二叉树，然后用一个数组类保存遍历的结果，这样在数组中节点就按顺序保存了，然后再来修改指针，虽然没有一点技术含量，但是最后竟然还通过了 哈哈哈。。。
TreeNode* Convert(TreeNode* pRootOfTree) { if (pRootOfTree == NULL) return pRootOfTree; vector<TreeNode*> result; Convert(pRootOfTree, result); return Convert(result); } void Convert(TreeNode* node,vector<TreeNode*>&result) { if (node->left != nullptr) Convert(node->left, result); result.push_back(node); if (node->right != nullptr) Convert(node->right, result); } TreeNode* Convert(vector<TreeNode*>& result) { for (int i = 0; i < result.size()-1; ++i) { result[i]->right = result[i + 1]; result[i+1]->left = result[i]; } return result[0]; }
第二种解法
第二天早上再来复刷这道题，写下了下面这种解法，并且也简单做了备注。
2、借助栈和数组类进行数据保存，最后修改指针指向
关键在于二叉树的层次遍历这一块
public: TreeNode* Convert(TreeNode* pRootOfTree) { if (pRootOfTree == nullptr) return nullptr; vector<TreeNode*> result; stack<TreeNode*> s; // 形成一个中序遍历的结果，并添加指针。 while (!s.empty() || pRootOfTree != nullptr) { if (pRootOfTree != nullptr) { s.push(pRootOfTree); pRootOfTree = pRootOfTree->left; } else { pRootOfTree = s.top(); s.pop(); result.push_back(pRootOfTree); pRootOfTree = pRootOfTree->right; } } // 修改链表指针指向。 for (int i = 0; i < result.size() - 1; ++i) { result[i + 1]->left = result[i]; result[i]->right = result[i+1]; } return result[0]; }
第三种解法
后来又去看了牛客评论里看到一些比较好的解法，自己仔细思考过后把他摘抄下来，就是下面的第 3 种解法，当时就觉得人与人之间脑子是有差距的。。。
3、借助栈进行节点保存，很厉害的一种写法
/* 这种做法，真的是...我TM服了。 1. 明确Convert函数的功能。 输入：输入一个二叉搜索树的根节点。 过程：将其转化为一个有序的双向链表。 输出：返回该链表的头节点。 2. 明确成员变量pLast的功能。 pLast用于记录当前链表的末尾节点。 3. 明确递归过程。 递归的过程就相当于按照中序遍历，将整个树分解成了无数的小树，然后将他们分别转化成了一小段一小段 的双向链表。再利用pLast记录总的链表的末尾，然后将这些小段链表一个接一个地加到末尾。 */ TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* head = NULL, * pre = NULL;//head 输出，pre记录上一次出栈值 stack<TreeNode*> s; while (pRootOfTree || !s.empty()) { while (pRootOfTree!=nullptr) { s.push(pRootOfTree); pRootOfTree = pRootOfTree->left; } if (!s.empty()) { pRootOfTree = s.top(); s.pop(); if (pre != NULL) { pre->right = pRootOfTree; pRootOfTree->left = pre; } else//pre为空，表示s第一次出栈，第一次出栈值为最左值，即输出值 { head = pRootOfTree; } pre = pRootOfTree; pRootOfTree = pRootOfTree->right; } } return head; }
看完亮评之后接着向下看，又看到另外一种解法，自己也做了一点记录。
第四种解法
4、复杂一点的递归做法
先将左子树变为有序的排序链表，再将右子树变为有序的链表，然后将当前结点插入在两个链表中间就可以了，需要注意左子树和右子树为空的情况。
TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree == NULL) return NULL; TreeNode* leftTree = Convert(pRootOfTree->left); // 将左子树变为排序链表 TreeNode* rightTree = Convert(pRootOfTree->right); // 将右子树变为排序链表 TreeNode* tmp = leftTree; if(tmp != NULL) { while(tmp->right) { tmp = tmp->right; } tmp->right = pRootOfTree; } pRootOfTree->left = tmp; pRootOfTree->right = rightTree; if(rightTree != NULL) rightTree->left = pRootOfTree; return(leftTree == NULL ? pRootOfTree:leftTree); }
第五种解法
看了上面的那些案例，自己也加以思考，写出了属于自己的最终简单递归法。
TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree == NULL) return pRootOfTree; pRootOfTree = ConvertNode(pRootOfTree); while(pRootOfTree->left) pRootOfTree = pRootOfTree->left; return pRootOfTree; } TreeNode* ConvertNode(TreeNode* root) { if(root == NULL) return root; if(root->left) { TreeNode *left = ConvertNode(root->left); while(left->right) left = left->right; left->right = root; root->left = left; } if(root->right) { TreeNode *right = ConvertNode(root->right); while(right->left) right = right->left; right->left = root; root->right = right; } return root; }
大概过了一个月时间后我开始慢慢二刷了，因为有了前面的铺垫，我很快就做出来了，并且破天荒的用两种方法直接做出来了。
二刷
二刷第一种方法、借助stack和vector
牛客网运行结果：运行时间：2ms 占用内存：408k
TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree == nullptr) return nullptr; stack<TreeNode*> st; vector<TreeNode*> result; while( !st.empty() || pRootOfTree != nullptr){ if(pRootOfTree != nullptr){ st.push(pRootOfTree); pRootOfTree = pRootOfTree->left; } else{ pRootOfTree = st.top(); st.pop(); result.push_back(pRootOfTree); pRootOfTree = pRootOfTree->right; } } for(int i = 0; i < result.size()-1; ++i){ result[i+1]->left = result[i]; result[i]->right = result[i+1]; } return result[0]; }
二刷第二种方法、依然是栈，不过节约了不少空间，记录这种做法，很棒
牛客网运行结果：运行时间：2ms 占用内存：484k
TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree == nullptr) return nullptr; stack<TreeNode*> st; vector<TreeNode*> result; TreeNode* head = nullptr,*pre = nullptr; while( !st.empty() || pRootOfTree != nullptr){ while(pRootOfTree != nullptr){ st.push(pRootOfTree); pRootOfTree = pRootOfTree->left; } if( !st.empty()){ pRootOfTree = st.top(); st.pop(); if(pre == nullptr){//表示第一次出栈，为最左值，记录下最小的元素 head = pRootOfTree; } else{ pre->right = pRootOfTree; pRootOfTree->left = pre; } pre = pRootOfTree; pRootOfTree = pRootOfTree->right; } } return head; }
所以啊，并没有什么捷径可以走，干就完了。
你可以参考我这样的刷题方式：首先自己先做，不会做或者做完了再去看高赞的解法，并且要看不止一种的高赞解法，尽量得去复现它和理解它。隔一段时间后再来二刷甚至是三刷就完事了。
如果你本来就不是很聪明或者ACM出生，直接来刷剑指offer是会有点吃力的，所以更要学会像我这样站在前人的肩膀上，多多利用前人给我们留下来的智慧结晶。
总有粉丝问我是如何刷题的？是怎么撑过 60 余场秋招笔试的？
喏，我就是这样刷题的，这就是我撑过 60 余场笔试的原因。
