BM30. [二叉搜索树与双向链表]

alt

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM30. 二叉搜索树与双向链表

https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=295&sfm=github&channel=nowcoder

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

返回值描述：

双向链表的其中一个头节点。

题目分析
这个题目看上去很难，想起来也很复杂，但是我告诉你这道题目其实就是一个中序遍历+翻转链表的变种，只要你会中序遍历和翻转链表就能轻松搞定这道题目

4->6->8->10->12->14->16这个顺序让你想起来什么这个不就是中序遍历吗？先不管题目该怎么解答我们只使用中序遍历的模板就开整！先不管先上模板再说。

//中序遍历
    private void inOrder(TreeNode root) {
        if (root == null)
            return;
        inOrder(root.left);
        //
        inOrder(root.right);

    }

二叉树中序遍历法遍历全树，依次添加链接，创建两个指针，一个指向题目中要求的链表头（maxLeft），一个指向当前遍历的前一结点（pre)。

具体步骤

首先递归到最左，初始化maxLeft与pre，然后往后遍历整棵树，依次连接pre与当前结点，并更新pre

1.遍历左子树
2.处理当前节点含义
3.遍历右字树

alt

还记得翻转链表吗？当时我们就要使用双指针pre节点和cur节点，这道题也不例外，同理也要是使用pre节点和cur节点，cur节点在二叉的入参中已经给出来了，并且给了定义就是pRootOfTree，那么题目要求我们返回什么呢？双向链表的其中一个头节点。那我们就返回定义一个最左头节点就好了maxLeft。先把先把中序遍历和定义的全局节点写出来。

TreeNode pre = null;
TreeNode maxLeft = null;

private void inOrder(TreeNode root) {
        if (root == null)
            return;
        inOrder(root.left);
        ................
        inOrder(root.right);
    }

翻转链表的条件是什么 while(cur!=null)，现在是中序遍历链接成为链表，想要连接链表是不是就需要判断前驱节点pre是不是空？如果空，是不是就应该将pre和maxLeft都赋值成为当前节点。这块有一个小细节就是maxLeft仅仅会赋值一次，因为仅有在最左叶子节点的时候才会赋值maxLeft；同理如果pre不为空直接执行连接逻辑即可，另外还要加记得向后继续遍历链表将pre=pRootOfTree

所有这道题目真的是非常的简单，中序遍历+翻转链表就能轻松搞定，很多题目真的想通了之后就是秒解

public class Solution {
    TreeNode pre = null;
    TreeNode maxLeft = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        inOrder(pRootOfTree);
        return maxLeft;
    }

private void inOrder(TreeNode root) {
        if (root == null)
            return;
        inOrder(root.left);
        if(pre == null){
          maxLeft = root;
          pre = root;
        }else{
          pre.right = root;
          root.left = pre;
          pre = root;
        }
        inOrder(root.right);
    }

}

class Solution {
public:
    TreeNode* head = NULL;  //返回的第一个指针，即为最小值，先定为null
    TreeNode* pre = NULL;   //中序遍历当前值的上一位，初值为最小值，先定为null
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree == NULL)
            return NULL;        //中序递归，叶子为空则返回
        Convert(pRootOfTree->left); //首先递归到最左最小值
        if(pre == NULL){       //找到最小值，初始化head与pre
            head = pRootOfTree;
            pre = pRootOfTree;
        }
        else{       //当前结点与上一结点建立连接，将pre设置为当前值
            pre->right = pRootOfTree;
            pRootOfTree->left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree->right);
        return head;
    }
};

复杂度分析