LeetCode426 将二叉搜索树转换为有序双向链表 & 剑指 Offer 36 二叉搜索树与双向链表

二叉搜索树转双向链表实现

• 标题
  • 答题过程
  • • 答案一：递归算法
    • 答案二：栈结构应用
    • 答案三：Morris 中序遍历方法

题目

解题

一道看似换汤不换药的「二叉树中序遍历」题目，对于对中序遍历概念尚不熟悉的读者，建议先前往 LeetCode94 二叉树的中序遍历 进行学习。

94 题要求按照中序遍历的顺序，将节点值以数组的形式输出。而本题的不同之处在于，需要构造一个循环双向链表结构。其中，left 指针等同于 prev 指针，right 指针等同于 next 指针，并且首尾节点需要相互连接（需记录 head 和 tail，在最后完成连接操作）。

因此，在将节点的 val 值添加至数组时，所执行的操