Jianbo Dai's

jz036.二叉搜索树与双向列表

 
  • Jun 21, 2020

题目链接

在搜索二叉树中，左子节点的值总是小于父节点的值，右子节点的值总是大于父节点的值。因此，我们在将二叉搜索树转换成排序双向链表时，原先指向左子节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每个节点。当遍历根节点的时候我们把树看成3部分：根节点，左子树和右子树。根据排序链表的定义，根节点将和它的左子树的最大的一个节点连接起来，同时还和右子树中最小的节点链接起来。而对于各个子树，过程是类似的，所以我们很容易就能想到用递归或者说分治算法。另外，我们还需要注意将双向链表的两端连接起来。这个算法的时间复杂度是O（N）,N为二叉树的节点数，中序遍历需要访问所有节点。;空间复杂度是O（N）,最差情况下，即树退化为链表时，递归深度达到N，系统使用 O(N) 栈空间。

class Solution:

    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return 
        self.pre = None
        self.dfs(root)
        self.head.left, self.pre.right = self.pre, self.head
        return self.head
        
    def dfs(self, cur):
        if not cur:
            return 
        self.dfs(cur.left)
        if self.pre: # 修改节点引用
            self.pre.right, cur.left = cur, self.pre
        else: # 记录头节点
            self.head = cur
        self.pre = cur # 保存 cur
        self.dfs(cur.right)
Search