1. 题目
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
2. 示例
3. 分析
1.不是重新构造链表，而是改变搜索二叉树的指针指向，使其成为排序循环链表
2.搜索二叉树是走中序排出来的
3.整个过程需要使用到递归，如何使用递归来解决呢？把搜索二叉树的左右子树期间，让cur的left指向双向链表的prev，prev的right指向cur，这就调整了原来的树结构，再让prev挪到cur的位置，准备下一次递归
4. 代码实现
1. /* 2. struct TreeNode { 3. int val; 4. struct TreeNode *left; 5. struct TreeNode *right; 6. TreeNode(int x) : 7. val(x), left(NULL), right(NULL) { 8. } 9. };*/ 10. class Solution { 11. public: 12. 13. //1.中序遍历 14. void InOrder(TreeNode* cur,TreeNode*& prev)//prev加引用，让全局只有一个prev，否则每层都有一个prev，那么上一层就拿不到下一层修改过的prev 15. { 16. if(cur == nullptr) 17. { 18. return; 19. } 20. 21. InOrder(cur->left,prev); 22. cur->left = prev;//cur的左指向prev 23. 24. if(prev) 25. { 26. prev->right=cur;//prev的右指向cur 27. } 28. 29. prev = cur;//prev挪到cur的位置，准备下一次递归 30. InOrder(cur->right,prev); 31. 32. } 33. 34. TreeNode* Convert(TreeNode* pRootOfTree) 35. { 36. if(pRootOfTree == nullptr) 37. { 38. return nullptr; 39. } 40. 41. TreeNode* prev = nullptr; 42. InOrder(pRootOfTree,prev);//中序遍历 43. 44. TreeNode* head = pRootOfTree; 45. 46. //找链表头节点 47. while(head->left) 48. { 49. head = head->left; 50. } 51. 52. return head; 53. } 54. };
