【LeetCode 109】有序链表转换二叉搜索树

蔚落 2022-11-29 03:10 149阅读 0赞

#### 题目描述 ####

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

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

示例:

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

#### 解题思路 ####

由于数组是有序递增排列的，所以我们可以从数组的中间开始查找。利用**递归+二分法**来解决这个问题。具体实现思路如下：

*  找出数组的中间元素，作为二叉树的根节点的值
 *  二叉树的左节点是`0—mid-1`的中间坐标对应的元素
 *  二叉树的右节点是`mid+1—arr.length-1`的中间坐标对应元素
 *  按照上面的规律进行地递归，直到数组元素遍历完

需要注意的是，最后的结果可能不唯一。

该算法的**时间复杂度为O(n)，空间复杂度为O(1)**。

#### 代码实现 ####

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
    /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
    /** * @param {ListNode} head * @return {TreeNode} */
    var sortedListToBST = function(head) { 
        const arr=[];
        while(head){ 
            arr.push(head.val)
            head = head.next
        }
        const resTree=function(left, right){ 
            if(left > right) return null
            const mid = Math.floor(left + (right - left)/2); 
            const res = new TreeNode(arr[mid]);
            res.left = resTree(left, mid-1);
            res.right = resTree(mid+1, right);
            return res
        }
        return resTree(0, arr.length-1) 
    };

#### 提交结果 ####

![在这里插入图片描述][20200819001622207.png]

[20200819001622207.png]: /images/20221124/4d3523ff374d4c6fa1f0ac377dfd8732.png?