剑指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 };