题目地址:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
题目大致意思是要把一棵二叉搜索树转换成排序双向循环链表,返回最小元素节点。每个节点左指针指向前驱结点,右节点指向后继节点。
利用二叉搜索树中序遍历为升序序列的性质,我们使用中序变量进行转换,递归实现。
需要考虑的问题是,对于一个节点,我们需要把它的左指针指向它的左子树的最大节点(如果存在),把左子树最大节点右指针指向该节点,这样做我们需要考虑边界情况,也就是首节点,首节点没有前驱。
为了返回,我们需要保存头节点,为了构造双向链表,我们需要保存前驱结点,并在递归中更新。
1 | /* |