将二叉搜索树转换成双向链表(实现及思路)

KLQ 2020-04-16 15:09:58 java常见问答 8456

你知道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实例,可以继续关注本站获取哦。