搜索二叉树转化为排序双向链表
题目描述:输入一棵二叉搜索树,现在要将该二叉搜索树转换成一个排序的双向链表。而且在转换的过程中,不能创建任何新的结点,只能调整树中的结点指针的指向来实现。
题目分析:要实现一个排序的双向链表,,首先想到的就是中序遍历。所以出现以下两种遍历修饰。
代码:
Node *g_prev = nullptr;
void SBTreeToLink(Node *root)
{
if(root != nullptr)
{
SBTreeToLink(root->left);
if(g_prev != nullptr)
g_prev->right = root;
root->left = g_prev;
g_prev = root;
SBTreeToLink(root->right);
}
}