你知道Java将一棵二叉搜索树，转换成一个排序的双向链表应该如何实现吗?下面就给大家分享3种实现方式和思想。
题目：
输入一棵二叉搜索树，将这颗二叉搜索树转换成一个排序的双向链表。
注：要求不可以创建任何新的结点，只可以调整树中结点指针的指向。
思路1：
直接用中序遍历，只要记录一个pre指针就可以了。
代码实现：
class Solution
{
public:
TreeNode * Convert(TreeNode * pRootOfTree)
{
if (pRootOfTree == nullptr) return nullptr;
TreeNode * pre = nullptr;
convertHelper(pRootOfTree, pre);
TreeNode * res = pRootOfTree;
while (res - > left)
res = res - > left;
return res;
}
void convertHelper(TreeNode * cur, TreeNode * & pre)
{
if (cur == nullptr) return;
convertHelper(cur - > left, pre);
cur - > left = pre;
if (pre) pre - > right = cur;
pre = cur;
convertHelper(cur - > right, pre);
}
};思路2：
1、明确Convert函数的功能。
输入：输入一个二叉搜索树的根节点。
过程：将其转化为一个有序的双向链表。
输出：返回该链表的头节点。
2、明确成员变量pLast的功能。
pLast用于记录当前链表的末尾节点。
3、明确递归过程。
递归的过程就相当于按照中序遍历，将整个树分解成了无数的小树，然后将他们分别转化成了一小段一小段的双向链表。再利用pLast记录总的链表的末尾，然后将这些小段链表一个接一个地加到末尾。
代码实现：
private TreeNode pLast = null;
public TreeNode Convert(TreeNode root)
{
if (root == null)
return null;
// 如果左子树为空，那么根节点root为双向链表的头节点
TreeNode head = Convert(root.left);
if (head == null)
head = root;
// 连接当前节点root和当前链表的尾节点pLast
root.left = pLast;
if (pLast != null)
pLast.right = root;
pLast = root;
Convert(root.right);
return head;
}思路3：
中序遍历
代码实现：
public class Solution
{
TreeNode head = null;
TreeNode realHead = null;
public TreeNode Convert(TreeNode pRootOfTree)
{
ConvertSub(pRootOfTree);
return realHead;
}
private void ConvertSub(TreeNode pRootOfTree)
{
if (pRootOfTree == null) return;
ConvertSub(pRootOfTree.left);
if (head == null)
{
head = pRootOfTree;
realHead = pRootOfTree;
}
else
{
head.right = pRootOfTree;
pRootOfTree.left = head;
head = pRootOfTree;
}
ConvertSub(pRootOfTree.right);
}
}以上的3种思路及实现你都了解了吗?你自己有什么样的想法呢?更多Java实例，可以继续关注本站获取哦。