我大意了，刚一放出来就上了牛客网头条了

标签：right TreeNode 客网 nullptr pRootOfTree result 刚一放头条 left

大家好，我是阿秀。

前段时间，我把自己的剑指 offer 刷题笔记发在牛客上了（文末分享PDF版本的笔记）。其实在牛客网上已经有很多类似的专栏了，不过为什么我的专栏能上头条呢？

我大意了，刚一放出来就上了牛客网头条了_nvidia

成功上首页

一个原因是可能长得帅，这我承认，但还是有其他原因的，且听我娓娓道来。

真实的原因

以下回答摘自本人在知乎上的回答：剑指offer，leetcode怎么刷？
https://www.zhihu.com/question/271458173/answer/1637905003

言归正传，刷剑指 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 余场笔试的原因。

虚假的原因

我大意了，刚一放出来就上了牛客网头条了_mooc_02

卑微求上头条

我大意了，刚一放出来就上了牛客网头条了_weex_03

成功啦

我大意了，刚一放出来就上了牛客网头条了_链表_04

我错了，下回还敢

结语

有玩牛客网的小伙伴可以直接去牛客：汇集牛客高赞解法的67道剑指offer

https://blog.nowcoder.net/zhuanlan/qmGzR0

另外阿秀也把自己的笔记整理成了PDF，后台回复【阿秀剑指offer笔记】就可以领取了。刷起来~

Hi，小伙伴你好，我是阿秀，一枚从底层慢慢爬到互联网大厂的程序员，公众号上每一篇原创文章都是我精心创作、慢慢打磨出来的，如果你觉得本文对你有所帮助，麻烦点亮一下「赞」和「」，也可以「分享」给需要的小伙伴，阿秀真的很需要你的点亮，十分感谢！

我大意了，刚一放出来就上了牛客网头条了_nvidia_05

“你只管努力，剩下的交给时间就好，我就是活生生的例子~”

标签：right,TreeNode,客网,nullptr,pRootOfTree,result,刚一放,头条,left
From： https://blog.51cto.com/u_16015370/6748796