输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：中序遍历，并用一个指向当前节点的上一个节点和当前节点的指向相互指向。
C++
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree == nullptr) return nullptr; TreeNode* pre = nullptr; convertHelper(pRootOfTree, pre); TreeNode* res = pRootOfTree; while(res ->left) //找双双向链表的首节点 res = res ->left; return res; } void convertHelper(TreeNode* cur, TreeNode*& pre) //中序遍历 { if(cur == nullptr) return; convertHelper(cur ->left, pre); cur ->left = pre; //当前节点的左指针 指向前面的pre节点 if(pre) pre ->right = cur; // pre节点的右指针指向后面的cur节点 pre = cur; // pre 后移 convertHelper(cur ->right, pre); } };
