面试题36. 二叉搜索树与双向链表

题目

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

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

image.png

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

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

image.png

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

注意：本题与主站 426 题相同：https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

注意：此题对比原题有改动。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

首先是递归，前序遍历。
但是问题是，在最后的结果中，root左边的不是root.left，这就需要把左子树和root相接的节点找出来，同理，右子树也要找出来。

我的解法

由于左右子树的处理方式不一样，所以只传root进行递归不够用，就加上了标记位isLeft，如果处理的节点是左节点，连接好之后，一直向右找到尾巴返回。

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root: return None
        last = self.convert(root, True)
        while root.left : root = root.left
        root.left = last
        last.right = root
        return root

    def convert(self, root, isLeft):
        if not root : return None
        if root.left: 
            root.left = self.convert(root.left, isLeft)
            root.left.right = root
        if root.right: 
            root.right = self.convert(root.right, not isLeft)
            root.right.left = root
        pLastNode = root
        if isLeft:
            while pLastNode.right : pLastNode = pLastNode.right
        else:
            while pLastNode.left : pLastNode = pLastNode.left
        return pLastNode

大佬解法

剑指面试题[36]——二叉搜索树与双向链表 - 挪罗儿的文章 - 知乎
https://zhuanlan.zhihu.com/p/105103682
我全都要，返回的时候直接把左右两边都返回，就不需要像我这样每次跑这么远去找头或者尾巴。

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root: return None
        l_head, r_tail = self.convert(root)
        l_head.left, r_tail.right = r_tail,l_head
        return l_head

    def convert(self, root):
        if root.left:
            l_head,l_tail = self.convert(root.left)
            l_tail.right = root
            root.left = l_tail
        else:
            l_head = root
        if root.right:
            r_head, r_tail = self.convert(root.right)
            r_head.left = root
            root.right = r_head
        else:
            r_tail = root

        return l_head, r_tail

总结

题目本身不难，花了太多时间。
一开始没有考虑左右子树不一样的问题，导致每次返回都是一样的，出错。
后来考虑到，传参判断是左子树还是右子树。
比较简单的写法是左右两个都返回。