大家好,我是阿秀。
前段时间,我把自己的剑指 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 余场笔试的原因。
虚假的原因
卑微求上头条
成功啦
我错了,下回还敢
结语
有玩牛客网的小伙伴可以直接去牛客:汇集牛客高赞解法的67道剑指offer
另外阿秀也把自己的笔记整理成了PDF,后台回复【阿秀剑指offer笔记】就可以领取了。刷起来~
Hi,小伙伴你好,我是阿秀,一枚从底层慢慢爬到互联网大厂的程序员,公众号上每一篇原创文章都是我精心创作、慢慢打磨出来的,如果你觉得本文对你有所帮助,麻烦点亮一下「赞」和「」,也可以「分享」给需要的小伙伴,阿秀真的很需要你的点亮,十分感谢!
“你只管努力,剩下的交给时间就好,我就是活生生的例子~”
标签:right,TreeNode,客网,nullptr,pRootOfTree,result,刚一放,头条,left From: https://blog.51cto.com/u_16015370/6748796