首页 > 其他分享 >leetcode 将有序数组转换为二叉搜索树

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

时间:2023-09-14 21:44:41浏览次数:38  
标签:node TreeNode val nums int 二叉 startIndex 数组 leetcode

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

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1:
image

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

示例 2:
image

输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

解题思路

二叉搜索树的特点是 当前节点左子树的所有节点都小于或等于自己,右子树的所有节点都大于等于资质
且搜索树上的每个节点都满足这个特征。

而给定的数组是升序的
那么给定数组中间的那个元素就是树的树顶,
然后基于上面那个元素的位置将数组一份为二,左子数组中间的元素就是左子树的树顶,右子数组的中间元素就是右子树的树顶。
以此类推(递归走起)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }

        if (nums.length == 1) {
            TreeNode root = new TreeNode();
            root.val = nums[0];
            return root;
        }

        TreeNode node = makeTree(nums, 0, nums.length-1);
        return node;
    }

    private TreeNode makeTree(int[] nums, int startIndex, int endIndex) {
        if (startIndex > endIndex) {
            return null;
        }
        
        TreeNode node = new TreeNode();
        node.val = nums[startIndex + (endIndex-startIndex)/2];

        node.left = makeTree(nums, startIndex, startIndex + (endIndex-startIndex)/2 - 1);


        node.right = makeTree(nums, startIndex + (endIndex-startIndex)/2 + 1, endIndex);
        return node;
    }
}

标签:node,TreeNode,val,nums,int,二叉,startIndex,数组,leetcode
From: https://www.cnblogs.com/gradyblog/p/17703553.html

相关文章

  • Java数组遍历
    publicclassbianli{publicstaticvoidmain(String[]args){int[]arr={11,22,33,44,55};printArray(arr);}publicstaticvoidprintArray(int[]arr){System.out.print("[");......
  • 二维数组的存储顺序、表示方法
    二维数组的存储顺序、表示方法先说一维数组:1.数组首地址也是第一个元素的首地址1#include<iostream>2usingnamespacestd;34intmain(){5intarr[5]={};6cout<<"arr="<<arr<<endl;7cout<<"&arr[0]=&q......
  • 【Java入门】交换数组中两个元素的位置
    在Java中,交换数组中的两个元素是基本的数组操作。下面我们将详细介绍如何实现这一操作,以及在实际应用中这种技术的重要性。一、使用场景在编程中,我们经常需要交换数组中的两个元素。例如,当我们需要对数组进行排序或者在某种算法中需要交换元素的位置。这种操作在数据结构、算法、......
  • 【Java入门】交换数组中两个元素的位置
    在Java中,交换数组中的两个元素是基本的数组操作。下面我们将详细介绍如何实现这一操作,以及在实际应用中这种技术的重要性。一、使用场景在编程中,我们经常需要交换数组中的两个元素。例如,当我们需要对数组进行排序或者在某种算法中需要交换元素的位置。这种操作在数据结构、算法......
  • 可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫
    P8946TheLostSymbol这种类型的dp的特点就是大部分转移形如\(f(i,j)\rightarrowf(i+1,j+1)\)之类的,并且当以上转移出现时原数组被清空,这就可以用一个deque来维护,然后对于全局赋值/全局加,需要对每个位置维护一个时间戳,并记录上一次赋值/加是什么时候,以便标记下传。(貌似......
  • Jquery 将 JSON 列表的 某个属性值,添加到数组中
    jquery将JSON列表的某个属性值,添加到数组中如果你有一个JSON列表,并且想要将每个对象的某个属性值添加到数组中,你可以使用jQuery的$.each()函数来遍历JSON列表,并获取所需的属性值。以下是一个示例代码:varjsonList=[{"name":"John","age":30,"city":"NewYork......
  • 洛谷OJ [P5018 对称二叉树] (深度优先搜索、二叉树、思维)
    P5018[NOIP2018普及组]对称二叉树题意:给定一棵树,树上的每个结点有一个权值,问你这棵树的子树中节点数最多的对称二叉树的节点数是多少?对称二叉树的定义如下:对于树中的每一个结点,要么没有子节点,要么既有左儿子,又有右节点,且对称位置的结点点权相等。输入格式:第一行......
  • 计算数组中最大值
    snum="345,231,56,786,1100,356,1200,300,685,111,134,765"functionGetMax(str)num=split(str,",")max=num(0)forii=0toubound(num)ifcint(num(ii))>cint(max)thenmax=num(ii)response.Write"num="&num(ii)&&......
  • c++ 实现 二叉树的 先序遍历,中序遍历 ,后序遍历
    遍历二叉树跟数组不同,树是一种非线性的数据结构,是由n(n>=0)个节点组成的有限集合。如果n==0,树为空树。如果n>0,树有一个特定的节点,叫做根节点(root)。 对于树这种数据结构,使用最频繁的是二叉树。每个节点最多只有2个子节点的树,叫做二叉树。二叉树中,每个节点的子节点作为根的两个子......
  • 剑指Offer面试题3题目二:不修改数组找出重复的数字
    一、题目在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长度为8的数组{2,3,5,4,3,2,6,7},那么对应的输出是重复的数字2或3。输入参数:一个整数数组numbers,......