109. 有序链表转换二叉搜索树（JS实现）

逃离我推掉我的手 2023-02-21 09:13 22阅读 0赞

## 1 题目 ##

> 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。  
> 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。  
> 示例:  
> 给定的有序链表： \[-10, -3, 0, 5, 9\],  
> 一个可能的答案是：\[0, -3, 9, -10, null, 5\], 它可以表示下面这个高度平衡二叉搜索树：  
> 0  
> /  
> \-3 9  
> / /  
> \-10 5

## 2 思路 ##

**这道题我是将链表转换为数组，然后再用递归的方法来划分数组构造二叉树的，题解有更巧妙的中序遍历递归构造数**

## 3代码 ##

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