解题思路
思路1 : 中序遍历,将节点放进vector中,再改链接关系,这很容易想出并解决,但这样明显不符合题意。
思路2:
这道题目要求将一个二叉搜索树转换成一个排序的双向链表,不创建新的节点,只调整指针。
二叉搜索树的特点是左子树的值都小于根节点,右子树的值都大于根节点,中序遍历可以得到一个升序的序列。
因此,我们可以利用中序遍历的顺序,将每个节点的左指针指向前一个节点,将每个节点的右指针指向后一个节点,从而形成一个双向链表。
我们需要用一个变量prev来记录前一个节点,初始为nullptr。然后我们递归遍历二叉树,每次访问到一个节点时,就修改它和prev的指针,并更新prev为当前节点。
最后,我们从根节点开始往左走,找到最左边的节点,即双向链表的头节点,返回即可。
举个栗子:
假设我们有这样一个二叉搜索树:
10 / \ 6 14 / \ / \ 4 8 12 16
我们先初始化prev为空,然后从根节点开始递归遍历二叉树。
首先我们遍历到4这个节点,它没有左子树,所以我们直接修改它的左指针指向prev(此时为空),然后将prev更新为4。
然后我们回到6这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为4),并将4的右指针指向6。然后将prev更新为6。
然后我们遍历到8这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为6),并将6的右指针指向8。然后将prev更新为8。
然后我们回到10这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为8),并将8的右指针指向10。然后将prev更新为10。
然后我们遍历到12这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为10),并将10的右指针指向12。然后将prev更新为12。
然后我们回到14这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为12),并将12的右指针指向14。然后将prev更新为14。
然后我们遍历到16这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为14),并将14的右指针指向16。然后将prev更新为16。
最后我们回到根节点10,并从它开始往左走,找到最左边的节点4,即双向链表的头节点。返回4即可。
此时二叉搜索树已经转换成了如下的双向链表:
代码—加注释
/* struct TreeNode { int val; // 节点的值 struct TreeNode *left; // 左子节点的指针 struct TreeNode *right; // 右子节点的指针 TreeNode(int x) : // 构造函数,初始化节点的值和子节点指针 val(x), left(NULL), right(NULL) { } };*/ class Solution { public: void InOrderConvert(TreeNode* cur, TreeNode*& prev) { if (cur == nullptr) // 如果当前节点为空,直接返回 return; InOrderConvert(cur->left, prev); // 递归遍历左子树 //这里cur出现的顺序就是中序 cur->left = prev; // 将当前节点的左指针指向前一个节点 if (prev) // 如果前一个节点不为空,将其右指针指向当前节点 prev->right = cur; prev = cur; // 更新前一个节点为当前节点 InOrderConvert(cur->right, prev); // 递归遍历右子树 } TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* prev = nullptr; // 初始化前一个节点为空 InOrderConvert(pRootOfTree, prev); // 调用辅助函数,中序遍历二叉树,并修改指针 TreeNode* head = pRootOfTree; // 初始化头节点为根节点 while (head && head->left) { // 循环找到最左边的节点,即双向链表的头节点 head = head->left; } return head; // 返回头节点 } };
本节完