leetcode链表之转换二叉树

109、有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例：

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

---

思路：

二叉搜索树需要保证父节点的值大于左节点的值，且小于右节点的值。

高度平衡则需要找到整个链表的中心，这样可以保证创造出来的子节点是平衡的。

需要找到链表的中心，这里可以采用快慢指针来处理，快指针每次走两步，慢指针每次走一步，当快指针或者快指针的下一个到达尾部的时候，这个慢指针指向的就是中间位置。

代码：

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        # 采用快慢指针找到left和right的中间结点
        def getMedia(left, right):
            fast = slow = left
            while fast != right and fast.next != right:
                fast = fast.next.next
                slow = slow.next
            return slow

        def buildTree(left, right):
            if left == right: return
            mid = getMedia(left, right)
            # 以中间结点为基准创建树
            root = TreeNode(mid.val, left=buildTree(left, mid), right=buildTree(mid.next, right))
            return root

        return buildTree(head, None)

114、二叉树展开为链表

题目

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例2：

输入：root = []
输出：[]

示例3：

输入：root = [0]
输出：[0]

---

思路：

题目要求展开后和二叉树的先序遍历顺序相同，并且需要直接在root结点上进行修改

很直观的想法是直接通过先序遍历将所有结点遍历出来，再拼接成单链表

代码：

class Solution:
    def flatten(self, root: TreeNode) -> None:
        if not root: return
        preorder = []
        stack = []
        node = root
        # 前序遍历并将所有节点存储在preorder中
        while node or stack:
            while node:
                preorder.append(node)
                stack.append(node)
                node = node.left
            node = stack.pop()
            node = node.right
        
        n = len(preorder)
        node = root
        # 遍历preorder，将所有节点拼接起来
        for i in range(1, n):
            node.left = None
            node.right = preorder[i]
            node = node.right