【C++二叉树】JZ36 二叉搜索树与双向链表
二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
思路分析：
- 根据题目要求可以看出将二叉搜索树转换为排序的双向链表就是中序遍历二叉搜索树。
- 在中序遍历的过程中将前后节点链起来即可。左指针指向前一个，右指针指向后一个。
- 中序遍历是递归实现的，要将节点和前驱、后继链起来，我们找不到他们的位置。只知道当前节点的位置。不知道前一个和后一个是谁。
- 这里可以考虑使用双指针来实现，prev指向前一个节点，cur指向当前节点。
- 当前节点cur的左指针指向前一个，但是cur的右指针要指向后一个没办法处理了。
- 当再走一步时，前一个节点的右指针就可以指向“当前节点”，就处理节点的右指针了。
图文分析：
代码实现：
注意：
prev传参要传引用，因为要保证在递归的过程中，prev能正确的使用，如果是传值，递归过程就找不到上一次递归使用的prev了。
总结：
主要使用了双指针的解题思想。