【基础篇 - Day 9】 2023-02-21 - 109. 有序链表转换二叉搜索树 （02. 链表 ）

[threedayAAAAA]

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

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

 

示例 1:

输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。 示例 2:

输入: head = [] 输出: []  

提示:

head 中的节点数在[0, 2 * 104] 范围内 -105 <= Node.val <= 105

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

方法一

思路

• 题目给出的链表是有序的，所以只需要将中间节点作为根节点，然后左半边侧右半边侧的链表递归下生成对应的左右子节点即可
• 编写一个将链表二分成三段的函数，
• 1. 获取中间节点的前一个节点（中前）、中间节点、中间节点的前一个节点（中后）
• 2. 中前节点.next ===> null
• 3. 中间节点.next ===> null
• 返回 【头节点、中间节点、中后节点】即为所求
• 然后对这三段进行递归调用即可

代码

function sortedListToBST(head: ListNode | null): TreeNode | null {
    if(!head){
        return null
    }
    const [,midNode, rightLinkHead] = binaryLink(head)
    let leftRoot = generatRootNode(midNode, head)
    let rightRoot = generatRootNode(midNode, rightLinkHead)
    return new TreeNode(midNode.val, leftRoot, rightRoot)
};

function generatRootNode(head: ListNode | null, startNode: ListNode | null): TreeNode | null {
    return startNode !== head ? sortedListToBST(startNode) : null
}

function binaryLink(head: ListNode | null): [ListNode | null, ListNode | null, ListNode | null] {
    let midIndex = Math.floor(getLinkLen(head) / 2)
    if(midIndex === 0){
        return [null, head, null]
    }
    const midePreNode = getTargetIndexNode(head, midIndex - 1)
    const mideNode = midePreNode?.next
    const mideNextNode = mideNode?.next
    if(midePreNode){
        midePreNode.next = null
    }
    if(mideNode){
        mideNode.next = null
    }
    return [head, mideNode, mideNextNode]
}

function getTargetIndexNode(head: ListNode | null, index: number): ListNode | null {
    let result = head
    while(result && index--){
        result = result.next
    }
    return result
}

function getLinkLen(head: ListNode | null): number{
    let result = 0
    let currentNode = head
    while(currentNode){
        result++
        currentNode = currentNode.next
    }
    return result
}

时空复杂度

• 时间复杂度： O(NLogN)
• 空间复杂度：O(logn)

方法二

思路

• 思路同方法一
• 不过方法一的主要耗时在于频繁的去获取中间节点，但是链表是无法随机读取的
• 所以转变下思路，原有的链表本身就是有序的，没必要按先序遍历的思路 先把中间节点找到了再构建两个子树
• 可以按中序的思路 ，先构建左子树 这样左子树构建完后，指针自然就到了中间节点

代码

function sortedListToBST(head: ListNode | null): TreeNode | null {
    if(!head){
        return null
    }

    function buildTree(start: number, end: number): TreeNode | null{
        if(start > end){
            return null
        }
        const midIndex = Math.floor((start + end + 1) / 2)
        const rootNode = new TreeNode()
        rootNode.left = buildTree(start, midIndex - 1)
        rootNode.val = head.val
        head = head.next
        rootNode.right = buildTree(midIndex + 1, end)
        return rootNode
    }
    return buildTree(0, getLinkLen(head) - 1)
}

function getLinkLen(head: ListNode | null): number{
    let result = 0
    let currentNode = head
    while(currentNode){
        result++
        currentNode = currentNode.next
    }
    return result
}

时空复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(logn)

[yunliuyan]

思路

• 快慢指针，寻找中节点
• 中序遍历递归

代码

function sortedListToBST(head: ListNode | null): TreeNode | null {
  if(!head) {
    return null;
  }
  // 最后一个虚拟尾节点为null
  return getTreeNode(head, null);
};
const getTreeNode = (head: ListNode, end: ListNode | null) => {
  if(head === end) {
    return null;
  }
  let slow = head;
  let fast = head;
  while(fast !== end && fast.next !== end) {
    slow = slow.next;
    fast = fast.next.next;
  }
  /** 此时slow为中节点 */
  const treeNode = new TreeNode(slow.val);
  treeNode.left = getTreeNode(head, slow);
  treeNode.right = getTreeNode(slow.next, end);
  return treeNode; 
}

复杂度分析

时间复杂度：O(nlogn) 空间复杂度: O(n)

[MiumMi]

思路

1. 遍历链表，构造成数组，获取数组中位数，中位数左边作为左子树，中位数右边作为右子树

2. 递归遍历左子树和右子树，执行相同操作，获取到最终的树

   代码

   
   /**
   * Definition for singly-linked list.
   * class ListNode {
   *     val: number
   *     next: ListNode | null
   *     constructor(val?: number, next?: ListNode | null) {
   *         this.val = (val===undefined ? 0 : val)
   *         this.next = (next===undefined ? null : next)
   *     }
   * }
   */

/**

• Definition for a binary tree node.
• class TreeNode {
• val: number
• left: TreeNode | null
• right: TreeNode | null
• constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
• this.val = (val===undefined ? 0 : val)
• this.left = (left===undefined ? null : left)
• this.right = (right===undefined ? null : right)
• }
• } */

function getNode (data: TreeNode[]) { if (!data.length) { return null; } let rootNodeIndex = Math.floor(data.length / 2); let rootNode = data[rootNodeIndex]; rootNode.left = getNode(data.slice(0, rootNodeIndex)); rootNode.right = getNode(data.slice(rootNodeIndex + 1)); return rootNode; }

function sortedListToBST(head: ListNode | null): TreeNode | null { if (!head) { return null; } const data = []; let tempNode = head; while(tempNode) { data.push(new TreeNode(tempNode.val)); tempNode = tempNode.next; } return getNode(data); };

---
### 分析
1. 时间复杂度: O(nlogn)
2. 空间复杂度：O(n)