文章目录

• 题目描述
• 解法1：非递归
• 解法2：递归

题目描述

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

解法1：非递归

采用中序遍历的思想，修改当前结点与前一遍历结点的指针指向

• 需要一个栈，一个头结点标志位，一个当前结点的前一结点
• 先向左压一溜，到头了，就设那个最左结点为头结点，因为它最小，置标志位为false
• 到其右边，继续压一溜，到空时，弹出栈顶作为当前结点，修改当前结点与前一遍历结点的指向即可
  

解法2：递归