专栏首页IT那个小笔记108 将有序数组转换为二叉搜索树

108 将有序数组转换为二叉搜索树

01

题目信息

题目地址: https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树

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

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

      0
     / \
   -3   9
   /   /
 -10  5

02

题解:递归(中序)

一个升序数组,转二叉树还是并且是搜索树(右子树小左子树),因此这个数组相当于是搜索树的中序遍历

对于示例的数组:[-10,-3,0,5,9],转化为二叉搜索树结果是有很多

比如:

      0
     / \
   -3   5
   /     \
 -10      9 
      5
     / \
   -3   9
   / \    
 -10  0    

题目当前是要得高度平衡的一个解(因此上面一个解是不满足的平衡的),因此尽量取中间作为根,就是最平衡的。

如果是偶数,取中间的两个任意的。如下要么-10为当前根而-3为它的右子节点,要么-3为当前根而-10就为它的左子节点

因此我们可以推出递归

public TreeNode sortedArrayToBST(int[] nums) {
    return recurrence(nums, 0, nums.length - 1);
}
//取根
public TreeNode recurrence(int[] nums, int left, int right) {
    if (left > right) return null;
    // 除法运算向下取整,所以偶数取左边
    int mid = (left + right) / 2;
    // 取到根节点
    TreeNode root = new TreeNode(nums[mid]);
    // 再判断左右两个树,取哪个根
    root.left = recurrence(nums, left, mid - 1);
    root.right = recurrence(nums, mid + 1, right);
    return root;
}

时间复杂度当然是O(n),平衡的缘故栈的深度为log2n因此空间复杂度为O(logn)

03

总结

总体来说还是比较好想的一个二分的这样一个东西,题目是求出满足条件的一解

int mid = (left + right) / 2;

这样取就得到的就是遇偶数取左边的解,如果加个1之后再除2就是取右了,或者加个随机数(0/1)。这样可以每次执行得到满足条件的树可能都不一样。

最后初级合集关于树这一章也结束了也是这个合集整个数据结构的篇章结束了,从开始对树这样的结构很生疏仅仅遍历操作就与线性数据结构有很大差别,到现在虽然短短5题已经对这样一个数据结构更熟悉了。从下个章节开始的就是关于算法思维向的篇章(排序、动态规划、数学等等)

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Leetcode】108. 将有序数组转换为二叉搜索树

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

    Leetcode名企之路
  • LeetCode 108. 将有序数组转换为二叉搜索树

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

    Michael阿明
  • Leetcode No.108 将有序数组转换为二叉搜索树

    给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度...

    week
  • ​LeetCode刷题实战108:将有序数组转换为二叉搜索树

    https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

    程序IT圈
  • 图解精选 TOP 面试题 004 | LeetCode 108. 将有序数组转换为二叉搜索树

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

    江不知
  • 将有序数组转换为二叉搜索树

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

    木子星兮
  • leetcode树之将有序数组转换为二叉搜索树

    这里采用递归的思路,先取l与r的中间值m,根据m构建一个TreeNode,然后通过递归buildTree(nums, l, m - 1)及buildTree(n...

    codecraft
  • leetcode树之将有序数组转换为二叉搜索树

    这里采用递归的思路,先取l与r的中间值m,根据m构建一个TreeNode,然后通过递归buildTree(nums, l, m - 1)及buildTree(n...

    codecraft
  • Swift 将有序数组转换为二叉搜索树 - LeetCode

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

    韦弦zhy
  • 将有序数组转化为二叉搜索树

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

    你的益达
  • 【leetcode刷题】T120-将有序数组转换为二叉搜索树

    https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

    木又AI帮
  • 有序链表转换二叉搜索树

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

    你的益达
  • 一天一大 leet(将有序数组转换为二叉搜索树)难度:简单-Day20200703

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

    前端小书童
  • 【Leetcode】109.有序链表转换二叉搜索树

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

    Leetcode名企之路
  • LeetCode 109. 有序链表转换二叉搜索树

    https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

    freesan44
  • 【小Y学算法】⚡️每日LeetCode打卡⚡️——29.将有序数组转换为二叉搜索树

    给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

    呆呆敲代码的小Y
  • leetcode538. 把二叉搜索树转换为累加树

    给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater

    程序员小王
  • leetcode136|把二叉搜索树转换为累加树

    给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或...

    码农王同学
  • 算法篇:树之转换为二叉搜索树

    https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

    灰子学技术

扫码关注云+社区

领取腾讯云代金券