6.3 数据结构---树（链表、数组、二叉树转换）

一、数组 VS 二叉树

1.有序数组转换为二叉搜索树

思路：递归 时间复杂度O(N) 空间复杂度O(1) 

nums为空，return None nums非空，nums[n/2]为中间元素，根结点，nums[:mid]为左子树， nums[mid+1:]为右子树

class Solution:
    def sortedArrayToBST(self, nums):
        if len(nums) == 0:
            return None

        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[0:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])

        return root

二、链表 VS 二叉树

1.有序链表转换为二叉搜索树 leetcode109

思路1：利用快慢指针的思想寻找链表中点，将其分为两个部分，再继续找左右两个新链表的中点。 当慢指针不与出发点重合时，说明这个子链的长度<3,此时只要把子链的右边节点（如果有的话） 作为左节点的右子树即可 时间复杂度O(N) 空间复杂度O(1)

class Solution:
    def sortedListToBST(self, head):
        def getMid(node):
            if not node:
                return

            slow = node
            fast = node
            pre_slow = None

            while fast.next and fast.next.next:
                fast = fast.next.next
                pre_slow = slow
                slow = slow.next

            if slow == node:#中心点=head,没有左子树
                return None,slow #返回左,中心点
            else: #中心点!=None
                pre_slow.next = None#左子树到slow前一个节点结束
                return node,slow

        left_head,mid_node = getMid(head)
        root = TreeNode(mid_node.val) #中心点
        right_head = mid_node.next

        root.left = self.sortedListToBST(left_head)
        root.right = self.sortedListToBST(right_head)
        return root

　　

2.二叉树转换为单向链表

题目：给定一个二叉树，将该二叉树就地转换为单链表，单链表中节点顺序为二叉树前序遍历顺序。

思路1：前序遍历二叉树，将节点指针push进入vector， 顺序遍历vector中的节点，链接相邻两节点，形成单链表。（不满足就地转换的条件）

思路2：

3.二叉树转换为双向链表

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的节点，只能调整节点的指向

思路：中序遍历假设当前遍历的节点为root，root的左子树已经被转换为双向链表，使用两个变量pHead与pEnd分别指向链表的头结点与尾结点。那么在遍历root节点的时候，只需要将root节点的lchild指向pEnd，把pEnd的rchild指向root，此时root节点就被加入到双向链表里了，因此，root变成了双向链表的尾结点。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Test:
    def __init__(self):
        self.pHead = None
        self.pEnd = None

    def inOrderBSTree(self,root):
        if root == None:
            return
        self.inOrderBSTree(root.left)
        root.left = self.pEnd #使当前节点的左孩子指向双向链表中最后一个节点
        if self.pEnd == None:#双向列表为空，当前遍历的节点为双向链表的头结点
            self.pHead = root
        else:#使双向链表中最后一个节点的右孩子指向当前节点
            self.pEnd.rchild = root
        self.pEnd = root#将当前节点设为双向链表中最后一个节点
        self.inOrderBSTree(root.right)