剑指offer——38二叉搜索树与双向链表

 1 class Solution {
 2 public:
 3     TreeNode* Convert(TreeNode* pRootOfTree)
 4     {
 5         TreeNode* head = nullptr;
 6         ConvertNode(pRootOfTree, head);//返回的head为指向双链表的尾节点
 7         while (head != nullptr && head->left != nullptr)//向前找到头节点
 8             head = head->left;
 9         return head;
10     }
11     void ConvertNode(TreeNode *cur, TreeNode *&pre)
12     {
13         if (cur == nullptr)return;
14         ConvertNode(cur->left, pre);//找到最左节点
15 
16         cur->left = pre;//左节点指向比他更小的节点
17         if (pre != nullptr)pre->right = cur;//更小的右节点指向后一个节点
18          
19         pre = cur;//然后更新双链表
20         ConvertNode(cur->right, pre);
21     }
22 };