426_将二叉搜索树转化为排序的双向链表

类型：链表

• 426. 将二叉搜索树转化为排序的双向链表 💛

  https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

  ❓ 将一个 二叉搜索树就地转化为一个已排序的双向循环链表 。左孩子作为前驱指针，右孩子作为后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。返回链表中最小元素的指针，作为头部。

  💡 递归

  递归是一种聚焦局部的思考方式。我们考虑搜索树中的一个结点，其左子树中的结点均比它小，其右子树中的结点均比它大。我们可以这么考虑，如果当前，左子树中的结点已经构建完成了一个双向链表，右子树中的结点也已经构建成为了一个双向链表。那么当前要做的就是，把当前结点，衔接在这两个双向链表中。

  # 官方实现
  class Solution:
      def treeToDoublyList(self, root: 'Node') -> 'Node':
          def helper(node):
              """
              Performs standard inorder traversal:
              left -> node -> right
              and links all nodes into DLL
              """
              nonlocal last, first
              if node:
                  # left
                  helper(node.left)
                  # node 
                  if last:
                      # link the previous node (last)
                      # with the current one (node)
                      last.right = node
                      node.left = last
                  else:
                      # keep the smallest node
                      # to close DLL later on
                      first = node        
                  last = node
                  # right
                  helper(node.right)
  
          if not root:
              return None
  
          # the smallest (first) and the largest (last) nodes
          first, last = None, None
          helper(root)
          # close DLL
          last.right = first
          first.left = last
          return first

  # 我的实现
  class Solution:
      def treeToDoublyList(self, root: 'Node') -> 'Node':
          if not root:
              return None
  
          leftHead = self.treeToDoublyList(root.left) if root.left else None
          rightHead = self.treeToDoublyList(root.right) if root.right else None
  
          if leftHead and rightHead:
              leftTail = leftHead.left
              rightTail = rightHead.left
  
              leftTail.right = root
              root.left = leftTail
              leftHead.left = rightTail
  
              root.right = rightHead
              rightHead.left = root
              rightTail.right = leftHead
              return leftHead
          elif not leftHead and not rightHead:
              root.right = root
              root.left = root
              return root
          elif leftHead:
              leftTail = leftHead.left
              leftTail.right = root
              root.left = leftTail
              root.right = leftHead
              leftHead.left = root
              return leftHead
          else:
              rightTail = rightHead.left
              root.left = rightTail
              root.right = rightHead
              rightHead.left = root
              rightTail.right = root
              return root