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

目录
  • 题目
  • 解题思路-基础
    • 代码实现
  • 解题思路-优化
    • 代码实现
  • 解题思路-进阶
    • 代码实现

题目

题目地址

给定一个单链表的头节点  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-有序链表转换二叉搜索树,更多关于前端算法有序链表转换二叉搜索树的资料请关注我们其它相关文章!

(0)

相关推荐

  • 前端算法题解leetcode36-有效的数独示例

    目录 题目 解题思路-分别处理 代码实现 解题思路-一次扫描判断所有 代码实现 题目 题目地址 请你判断一个 9 x 9 的数独是否有效.只需要 根据以下规则 ,验证已经填入的数字是否有效即可. 数字 1-9 在每一行只能出现一次. 数字 1-9 在每一列只能出现一次. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次.(请参考示例图) 注意: 一个有效的数独(部分已被填充)不一定是可解的. 只需要根据以上规则,验证已经填入的数字是否有效即可. 空白格用 '.' 表示. 示例 1:

  • LeetCode 刷题 Swift 两个数组的交集

    目录 题目 方法一:两个集合 思路及解法 代码 复杂度分析 方法二:排序 + 双指针 思路及解法 代码 复杂度分析 题目 给定两个数组 nums1 和 nums2,返回 它们的交集 .输出结果中的每个元素一定是 唯一 的.我们可以 不考虑输出结果的顺序 . 示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2] 示例 2: 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [9,4] 解释: [4,9] 也是可

  • LeetCode 题解 Swift 有效的完全平方数

    目录 题目 方法一:使用内置的库函数 思路及解法 复杂度分析 方法二:暴力 思路及解法 代码 复杂度分析 方法三:二分查找 思路及解法 细节 代码 复杂度分析 题目 给定一个 正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 true,否则返回 false. 进阶:不要 使用任何内置的库函数,如 sqrt. 示例 1: 输入: num = 16 输出: true 示例 2: 输入: num = 14 输出: false 方法一:使用内置的库函数 思路及解法 根据完全平方数的性

  • 前端算法题解leetcode114二叉树展开为链表

    目录 正文 解题思路-基础 代码实现 解题思路-进阶 代码实现 正文 题目地址 给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null . 展开后的单链表应该与二叉树 先序遍历 顺序相同. 示例 1: 输入: root = [1,2,5,3,4,null,6]输出: [1,null,2,null,3,null,4,null,5,null,6] 示例 2: 输入: root

  • 前端算法题解leetcode49-字母异位词分组

    目录 题目 解题思路 代码实现 题目 题目地址 给你一个字符串数组,请你将 字母异位词 组合在一起.可以按任意顺序返回结果列表. 字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次. 示例 1: 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],[

  • 前端算法题解 leetcode50-Pow(x, n)

    目录 题目 解题思路-分情况讨论 代码实现 解题思路-分治 代码实现 题目 题目地址 实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn ). 示例 1: 输入: x = 2.00000, n = 10 输出: 1024.00000 示例 2: 输入: x = 2.10000, n = 3 输出: 9.26100 示例 3:. 输入: x = 2.00000, n = -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25 提示: -100.0

  • 前端算法leetcode109题解有序链表转换二叉搜索树

    目录 题目 解题思路-基础 代码实现 解题思路-优化 代码实现 解题思路-进阶 代码实现 题目 题目地址 给定一个单链表的头节点  head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树. 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1. 示例 1: 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度平衡的二叉搜索树.

  • C++实现LeetCode(109.将有序链表转为二叉搜索树)

    [LeetCode] 109.Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary

  • 剑指Offer之Java算法习题精讲字符串与二叉搜索树

    题目一 解法 class Solution { public boolean repeatedSubstringPattern(String a) { for (int i = 1; i <=a.length()/2 ; i++) { String s = a.substring(0, i); StringBuffer sb = new StringBuffer(); while (sb.length()<a.length()){ sb.append(s); } if(sb.toString(

  • C++实现LeetCode(108.将有序数组转为二叉搜索树)

    [LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in wh

  • C++数据结构之二叉搜索树的实现详解

    目录 前言 介绍 实现 节点的实现 二叉搜索树的查找 二叉搜索树的插入 二叉搜索树的删除 总结 前言 今天我们来学一个新的数据结构:二叉搜索树. 介绍 二叉搜索树也称作二叉排序树,它具有以下性质: 非空左子树的所有键值小于其根节点的键值 非空右子树的所有键值大于其根节点的键值 左,右子树都是二叉搜索树 那么我先画一个二叉搜索树给大家看看,是不是真的满足上面的性质. 我们就以根节点6为例子来看,我们会发现比6小的都在6的左边,而比6大的都在6的右边.对于6的左右子树来说,所有的节点都遵循这个规则.

  • Python二叉搜索树与双向链表转换算法示例

    本文实例讲述了Python二叉搜索树与双向链表转换算法.分享给大家供大家参考,具体如下: 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表.要求不能创建任何新的结点,只能调整树中结点指针的指向. 普通的二叉树也可以转换成双向链表,只不过不是排序的 思路: 1. 与中序遍历相同 2. 采用递归,先链接左指针,再链接右指针 代码1,更改doubleLinkedList,最后返回list的第一个元素: class TreeNode: def __init__(self, x): s

  • Java C++ 算法题解leetcode669修剪二叉搜索树示例

    目录 题目要求 思路一:模拟迭代 Java C++ 思路二:递归 Java C++ Rust 题目要求 思路一:模拟迭代 依次判断每个节点是否合法: 首先找出结果的根,若原根小了就拉右边的过来,大了拉左边的过来做新根: 然后分别判断左右子树的大小,由于二叉搜索树的性质,子树只需要判断一边就好: 左子树判断是否>low,合法就向左下走,不合法往右下: 右子树判断是否<high,合法就向右下走,不合法往左下. Java class Solution { public TreeNode trimBS

  • Python二叉搜索树与双向链表转换实现方法

    本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.

  • C++如何将二叉搜索树转换成双向循环链表(双指针或数组)

    目录 二叉搜索树转换成双向循环链表 二叉搜索树与双向链表(C++中等区) 解题思路 代码展示 二叉搜索树转换成双向循环链表 本文解法基于性质:二叉搜索树的中序遍历为 递增序列 . 将二叉搜索树 转换成一个 “排序的循环双向链表”,其中包含三个要素: 1.排序链表:节点应从小到大排序,因此应使用 中序遍历 2.“从小到大”访问树的节点.双向链表:在构建相邻节点的引用关系时,设前驱节点 pre 和当前节点 cur , 不仅应构建 pre.right= cur,也应构建 cur.left = pre

  • Javascript实现从小到大的数组转换成二叉搜索树

    废话不多说了,直接给大家贴代码了,具体代码如下所示: var Array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; var Tree = createTree(Array); console.log(Tree); // 构造一个节点 function Node(nodeData, leftData, rightData) { this.nodeData = nodeData; this.leftData = leftData; this.rightData = rig

随机推荐