链表训练9：将搜索二叉树转换成双向链表

【题目描述】

对于二叉树的节点来说，有本身的值域，有指向左孩子和右孩子的两个指针；对双向链表的节点来说，有本身的值域，有指向上一个节点和下一个节点的指针。在结构上，两种结构有相似性，现有一棵搜索二叉树，请将其转为成一个有序的双向链表。
　
节点定义：

class Node2{
    public int value;
    public Node2 left;
    public Node2 right;

    public Node2(int value) {
        this.value = value;
    }
}

例如：

这棵二查搜索树转换后的双向链表从头到尾依次是 1～9。对于每一个节点来说，原来的 right 指针等价于转换后的 next 指针，原来的 left 指针等价于转换后的 last 指针，最后返回转换后的双向链表的头节点。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【难度】

尉：★★☆☆

【解答】

方法一：采用队列辅助

如果用一个队列来辅助的话，还是挺容易。采用中序遍历的方法，把二叉树的节点全部放进队列，之后在逐一弹出来连接成双向链表。

代码如下

    public static Node2 convert1(Node2 head) {
        Queue queue = new LinkedList<>();
        //将节点按中序遍历放进队列里
        inOrderToQueue(head, queue);
        head = queue.poll();
        Node2 pre = head;
        pre.left = null;
        Node2 cur = null;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            pre.right = cur;
            cur.left = pre;
            pre = cur;
        }
        pre.right = null;
        return head;
    }

    private static void inOrderToQueue(Node2 head, Queue queue) {
        if (head == null) {
            return;
        }
        inOrderToQueue(head.left, queue);
        queue.offer(head);
        inOrderToQueue(head.right, queue);
    }

这种方法的时间复杂度为 O(n), 空间复杂度也为 O(n)。

方法2：通过递归的方式

在之前打卡的9道题中，几乎超过一般都用到了递归，如果这些题目使用的递归大家都理解了，并且能够自己独立写出代码了，那么我相信大家对递归的思想、使用已经有一定的熟练性。

我们假设函数conver的功能就是把二叉树变成双向链表，例如对于这种一棵二叉树：

经过conver转换后变成这样：

注意，转换之后，把最右边节点的right指针指向了最左边的节点的。

对于下面这样一颗二叉树：

采用conver函数分别对左右子树做处理，结果如下：

之后，再把他们连接起来

了解了基本原理之后，直接看代码吧。

    public static Node2 conver(Node2 head) {
        if (head == null) {
            return head;
        }
        Node2 leftE = conver(head.left);
        Node2 rightE = conver(head.right);
        Node2 leftB = leftE != null ? leftE.right : null;
        Node2 rightB = rightE != null ? rightE.right : null;
        if (leftE != null && rightE != null) {
            leftE.right = head;
            head.left = leftE;
            head.right = rightB;
            rightB.left = head;
            rightE.right = leftB;
            return rightE;
        } else if (leftE != null) {
            leftE.right = head;
            head.left = leftE;
            head.right = leftB;
            return head;
        } else if (rightE != null) {
            head.right = rightB;
            rightB.left = head;
            rightE.right = head;
            return rightE;
        } else {
            head.right = head;
            return head;
        }
    }

时间复杂度为O(n),空间复杂度为O(h)，其中h是二叉树的高度。

原理虽然不难，但写起代码，还是有挺多细节需要注意的，所以一直强调，有时间的话，一定要自己手打一遍代码，有时你以为自己懂了，可能在写代码的时候，发现自己并没有懂，一写就出现很多bug。

如果喜欢本网站{https://www.iamshuaidi.com), 那么可以把该网站分享给其他人，帅地正在疯狂更新中….

帅地永久会员

收藏 海报 分享链接