LeetCode算法题——将有序数组转换成二叉搜索树（Java实现）

前言题目解题思路和具体实现过程思路具体代码 总结

前言

今天是每日一题的第二天啦！

题目

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

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

示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree

解题思路和具体实现过程

思路

其实在刚刚看到题目时，我是懵的 ？？？ 后来发现，其实就我想复杂了，其实这道题目的意思就是让我们把这个数组转换成一颗二叉树。而且对这个二叉树的要求就是：每个节点 的左右两个子树的高度差的绝对值不超过 1并且这个二叉树是二叉搜索树，而数组又是升序排列的。因此很容易想到，把数组中间的那个数作为根结点，这样左右两边的节点数就是一样的或者差1。并且左边是小的数，右边是大数，刚好符合二叉搜索树的特点。再把左边剩余的节点按照刚刚的思路继续，右边一样ok，一颗高度平衡的二叉树就完成了。

这其实就是递归的思想

具体代码

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode sortedArrayToBST(int[] num) { if (num.length == 0) return null; return recursiveNodeGenerateBST(num, 0, num.length - 1); } public TreeNode recursiveNodeGenerateBST(int[] num, int start, int end) {//递归 if (start > end) return null; int mid = (start + end) /2; //中间的数为根节点 TreeNode root = new TreeNode(num[mid]); //左右两边递归 root.left = recursiveNodeGenerateBST(num, start, mid - 1); root.right = recursiveNodeGenerateBST(num, mid + 1, end); return root; } }

总结

首先我懵的点就是看到二叉搜索树，忘记了这个概念。递归方法虽然简单，但是耗费的内存还是很大的。

什么是二叉搜索树？ 二叉搜索树又称又称二叉查找树或二叉排序树。对于二叉树中的每个节点X，它的左子树中所有项的值都小于X中的项，它的右子树中所有项的值大于X中的项。这样的二叉树是二叉查找树。

关于具体的二叉搜索树介绍，下面是我参考的资料： 【什么是二叉查找树】https://www.cnblogs.com/54chensongxia/p/11567886.html