面试题36. 二叉搜索树与双向链表（中）& LeetCode 426. 将二叉搜索树转化为排序的双向链表（中）

我们可以把树分为3部分：根节点、左子树和右子树，然后把左子树中最大的节点、根节点、右子树中最小的节点链接起来。至于如何把左子树和右子树内部的节点链接成链表，那和原来的问题的实质是一样的，因此可以递归解决。解决这个问题的关键在于把一个大的问题分解成几个小问题，并递归地解决小问题。

Question

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

bstdlloriginalbst.png

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。 “head” 表示指向链表中有最小元素的节点。

bstdllreturndll

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

测试用例

功能测试（输入的二叉树是完全二叉树；所有节点都没有左/右子树的二叉树：只有一个节点的二叉树）。 特殊输入测试（指向二叉树根节点的指针为 nullptr 指针）。

本题考点

考查应聘者分析复杂问题的能力。无论是二叉树还是双向链表，都有很多指针。要实现这两种不同数据结构的转换，需要调整大量的指针，因此这个过程会很复杂。为了把这个复杂的问题分析清楚，我们可以把树分为3部分：根节点、左子树和右子树，然后把左子树中最大的节点、根节点、右子树中最小的节点链接起来。至于如何把左子树和右子树内部的节点链接成链表，那和原来的问题的实质是一样的，因此可以递归解决。解决这个问题的关键在于把一个大的问题分解成几个小问题，并递归地解决小问题。 考查应聘者对二叉树和双向链表的理解及编程能力。

Intuition

Snipaste_2020-05-10_18-44-17

理论上有可能实现二叉搜索树和排序双向链表的转换。在搜索二叉树中，左子节点的值总是小于父节点的值，右子节点的值总是大于父节点的值。因此，我们在将二叉搜索树转换成排序双向链表时，原先指向左子节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。

中序遍历算法的特点是按照从小到大的顺序遍历二叉树的每个节点。当遍历到根节点的时候，我们把树看成3部分：值为10的节点；根节点值为6的左子树；根节点值为14的右子树。根据排序链表的定义，值为10的节点将和它的左子树的最大一个节点（值为8的节点）链接起来，同时它还将和右子树最小的节点（值为12的节点）链接起来，如图4.16所示。

Snipaste_2020-05-10_18-44-05

按照中序遍历的顺序，1. 当我们遍历转换到根节点（值为10的节点）时，它的左子树已经转换成一个排序的链表了，并且处在链表中的最后一个节点是当前值最大的节点。 2. 我们把值为8的节点和根节点链接起来，此时链表中的最后一个节点就是10了。3. 接着我们去遍历转换右子树，并把根节点和右子树中最小的节点链接起来。至于怎么去转换它的左子树和右子树，由于遍历和转换过程是一样的，我们很自然地想到可以用递归。

Code

  • 剑指offer版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node': 
        if root == None:
            return None
        if not root.left and not root.right:
            return root
        
        # 处理左子树
        self.treeToDoublyList(root.left)
        left = root.left


        # 连接根与左子树最大节点
        if left:
            while left.right:
                left = left.right
            root.left, left.right = left, root
        
        # 处理右子树
        self.treeToDoublyList(root.right)
        right = root.right

        # 连接根与右子树最小节点
        if right:
            while right.left:
                right = right.left
            root.right, right.left = right, root
        
        while root.left:
            root = root.left
        
        return root
  • LeetCode版本，要求双向链表是循环的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if not cur: return
            dfs(cur.left) # 递归左子树
            if self.pre: # 修改节点引用
                self.pre.right, cur.left = cur, self.pre
            else: # 记录头节点，到达树的最左下角叶子了
                self.head = cur
            self.pre = cur # 保存 cur
            dfs(cur.right) # 递归右子树
        
        if not root: return
        self.pre = None
        dfs(root)
        self.head.left, self.pre.right = self.pre, self.head
        return self.head

参考连接 作者：jyd 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。