题目描述

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

---

思路：

利用中序遍历的特性，从小到大遍历二叉树每一个结点。

修改中序遍历，在在其中加入一个前驱结点

遍历左子树

前驱结点右指针指向当前结点

当前结点指向左指针指向前驱结点

前驱 = 当前

遍历右子树

 

此时遍历结果pre指针指向的是链表尾，如果将上面的左右反过来，则直接返回pre即正确的答案。

class Solution{  public:    TreeNode *preNode = NULL;    TreeNode *Convert(TreeNode *curNode)    {        if (curNode == NULL)            return NULL;        Convert(curNode->right);        if (preNode)        {            preNode->left = curNode;            curNode->right = preNode;        }        preNode = curNode;        Convert(curNode->left);        return preNode;    }};