题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点,只能调整树中结点指针的指向。
注意
- 需要返回双向链表最左侧的节点。
例如,输入下图中左边的二叉搜索树,则输出右边的排序双向链表。
算法1
在中序遍历二叉树的过程中,记录前驱结点并不断更新,有了前驱后继关系便可修改结点的左右指针指向。
时间复杂度$O(n)$,空间复杂度$O(n)$
C++ 代码
class Solution {
public:
TreeNode *pre, *head; // 表示前驱结点,链表头结点
TreeNode* convert(TreeNode* root) {
if (!root) return NULL;
inOrder(root);
return head;
}
void inOrder(TreeNode *root) {
if (!root) return ;
inOrder(root->left);
if (pre) pre->right = root;
else head = root; // 此时,root为BST的最小值,即链表的头结点
root->left = pre;
pre = root; // 更新前驱结点
inOrder(root->right);
}
};
算法2
记录中序遍历序列,结果存在数组中,遍历该序列修改左右指针。
时间复杂度$O(n)$,空间复杂度$O(n)$
C++ 代码
class Solution {
public:
vector<TreeNode *> list;
TreeNode* convert(TreeNode* root) {
if (!root) return nullptr;
// 得到中序遍历序列
inOrder(root);
int size = list.size();
// 修改右指针
for (int i = 0; i < size - 1; ++i) {
list[i]->right = list[i + 1];
}
// 修改左指针
for (int i = 1; i < size; ++i) {
list[i]->left = list[i - 1];
}
return list[0];
}
void inOrder(TreeNode *root) {
if (!root) return;
inOrder(root->left);
list.push_back(root);
inOrder(root->right);
}
};
算法3
方法1中,pre在中序遍历结束指向链表的尾结点,为此需要额外记录头结点head。那么如果我们从后向前遍历呢?即按照right $\Rightarrow$ root $\Rightarrow$ left遍历二叉搜索树即从大到小从后往前遍历,遍历到最后一个结点既是我们要返回的头结点。
时间复杂度$O(n)$,空间复杂度$O(n)$
C++ 代码
class Solution {
public:
TreeNode *nxt;
TreeNode* convert(TreeNode* root) {
if (!root) return nullptr;
convert(root->right);
if (nxt) nxt->left = root, root->right = nxt;
nxt = root;
convert(root->left);
return nxt;
}
};