剑指offer最新版

剑指offer最新版

先介绍下自己吧，我是普通双非学校的计算机毕业生，2021年秋招的时候一共投递过 94 家公司，共计笔试59场，最多一天做了5场笔试，那天差点去世了。

找工作结果

最终成功走到了6家公司的offer环节：字节跳动研发岗SP、华为通用软件开发、百度C++研发岗、B站后端研发岗、深信服C++研发岗以及农业银行研发岗，最后签了字节跳动，去自己心心念念的大厂贡献自己的头发了~

面试暂且不说，我能够笔试 54 场的底气在哪里？就是因为我刷了 3 遍的剑指 offer 和 以 75%+ 的正确率刷了300+ 的leetcode算法题。上一下自己在 2019.8 - 2019.12那段时候的leetcode刷题记录吧。

在 11.13 号那天最疯狂，我一晚上提交了 29 次，清楚地记得刷了 7 道题，最后一道题卡了我 2 个多小时才做出来，回去睡觉的时候也是半夜一两点之后了。

言归正传，刷剑指offer的时候我刷了3遍，牛客平台2遍，leetcode平台1遍因为有些题目一样，但是平台后台设置的检测案例不一样，总的来说感觉还是leetcode的后台案例更多一些更全面一些，想的更周到一些，建议去leetcode刷剑指offer。

就拿剑指offer第 26 题作为例子来说吧。

NO26、二叉搜索树与双向链表 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能 调整树中结点指针的指向。

以下是我当时刷题时的笔记记录

第一种解法

第一天晚上我是写了下面第 1 种方法并且做了笔记的，当时还觉得不可思议，因为比自己想象中的要简单好多。

1、最笨的一种写法，这也是最容易理解的一种方法了

中序遍历二叉树，然后用一个数组类保存遍历的结果，这样在数组中节点就按顺序保存了，然后再来修改指针，虽然没有一点技术含量，但是最后竟然还通过了 哈哈哈。。。

TreeNode* Convert(TreeNode* pRootOfTree)

{

if (pRootOfTree == NULL) return pRootOfTree;

vector result;

Convert(pRootOfTree, result);

return Convert(result);

}

void Convert(TreeNode* node,vector&result) {

if (node->left != nullptr)

Convert(node->left, result);

result.push_back(node);

if (node->right != nullptr)

Convert(node->right, result);

}

TreeNode* Convert(vector& 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 result;

stack 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、借助栈进行节点保存，很厉害的一种写法

我服啦，采用的是跟剑指offer上一样的写法

1. 明确Convert函数的功能。

输入：输入一个二叉搜索树的根节点。

过程：将其转化为一个有序的双向链表。

输出：返回该链表的头节点。

2. 明确成员变量pLast的功能。

pLast用于记录当前链表的末尾节点。

3. 明确递归过程。

递归的过程就相当于按照中序遍历，将整个树分解成了无数的小树，然后将他们分别转化成了一小段一小段的双向链表。再利用pLast记录总的链表的末尾，然后将这些小段链表一个接一个地加到末尾。

TreeNode* Convert(TreeNode* pRootOfTree)

{

TreeNode* head = NULL, * pre = NULL;//head 输出，pre记录上一次出栈值

stack 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 st;

vector 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 st;

vector 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或者leetcode是会有点吃力的，所以更要学会像我这样站在前人的肩膀上，多多利用前人给我们留下来的智慧结晶。

另外求波关注啊@阿秀，最近疯狂在知乎划水，哈哈

顺便推荐一下我看过的算法书吧。

四颗星，挺有意思的一本书，适合作为初学者去看。

四颗星，这本可以作为数据结构的入门书，当然了你要是真心想学好，还是去看严奶奶的那本数据结构吧。

五颗星，这本书超棒，是国内大神巫泽俊翻译的国际顶尖ACMer的结晶之作！超棒！！！！

四颗星，这本书也不错，是华中科技大学的大佬左程云写的，很厉害，里面很多经典题。

PS

个人刷题笔记已经放出来了，有需要的可以去取一波阿秀：我大意了啊，刷题笔记一放出来就上了牛客网头条了​zhuanlan.zhihu