前端算法有序链表转换二叉搜索树

时间:2022-09-29 前端_奔跑的蜗牛人气:0

题目

题目地址

给定一个单链表的头节点 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

解题思路-基础

本题要求我们将给定的有序链表转为高度平衡的二叉搜索树，所以我们要保证每个子树的左子树的值都比它小，右子树的值都比它大，同时高度差不超过1。

因为给定的链表是升序的，所以我们遍历链表节点将节点值存入数组，这样就得到了一个升序的数组。然后取数组的中间节点为根节点的值，左边的都是小于它的值，右边的都是大于它的值，再通过左右两边的数值去构造当前节点的左右子树。最后当所有值都处理完，就构造完成了一颗高度平衡的二叉搜索树。

代码实现

var sortedListToBST = function(head) {
  if(head === null){
      return null
  }
  const list = []
  while(head){
      list.push(head.val)
      head = head.next
  }
  function buildTree(list){
      const len = list.length
      if(len===0){
          return null
      }
      const mid = len>>1
      const nodeVal = list[mid]
      const l = list.slice(0,mid)
      const r = list.slice(mid+1)
      return new TreeNode(nodeVal,buildTree(l),buildTree(r))
  }
  return buildTree(list)
};

解题思路-优化

上面的实现中我们每次都要切割 list 数组，其实可以更换为记录左右下标的方式，即省去了切割数组的过程，又不用每次创建子数组。

代码实现

var sortedListToBST = function(head) {
  if(head === null){
      return null
  }
  const list = []
  while(head){
      list.push(head.val)
      head = head.next
  }
  function buildTree(l,r){
      if(l>r){
          return null
      }
      const mid = (l+r)>>1
      const nodeVal = list[mid]
      return new TreeNode(nodeVal,buildTree(l,mid-1),buildTree(mid+1,r))
  }
  return buildTree(0,list.length-1)
};

解题思路-进阶

上面的实现方式时、空复杂度都是 O(nlogn) O(logn)，但是第二种做了进一步优化，实际表现会更好一点。而下面的实现方式时、空复杂度为：O(n) O(logn)。

这里我们转换思路，不去首先构造根节点，而是采用中序遍历的顺序构造目标二叉树，这样构造的顺序就可以和遍历链表的顺序吻合，达到在遍历链表的过程完成构造二叉树。

代码实现

const sortedListToBST = (head) => {
    if (head == null){
        return null
    }
    let len = 0
    let cur = head
    while (head) {
        len++
        head = head.next
    }
    function buildTree(l,r){
        if (l > r){
            return null
        }
        const mid = (l + r) >>> 1
        const leftTree = buildTree(l, mid - 1)
        const node = new TreeNode(cur.val)
        node.left = leftTree
        cur = cur.next           
        node.right = buildTree(mid + 1, r)
        return node
  }
  return buildTree(0, len - 1)
};

至此我们就完成了 leetcode-109-有序链表转换二叉搜索树，更多关于前端算法有序链表转换二叉搜索树的资料请关注其它相关文章！

加载全部内容