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

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

题目描述:给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例说明请见LeetCode官网。
【LeetCode-108-将有序数组转换为二叉搜索树】来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一:递归
根据二叉搜索树的性质,因为给定的数组是按升序排列的,所以可以确定数组num即为该二叉搜索树的中序遍历序列,为了得到一颗平衡的二叉树,取数组中间位置的节点作为根节点,这样,左右子树的节点较为平衡,具体处理过程如下:
  • 调用递归方法,初始的起始位置为数组的长度;
  • 当起点位置大于终点位置时,说明节点已经遍历完了,直接返回空树;
  • 获取中间位置的值作为根节点,这样左右子树的节点树是比较均衡的;
  • 然后递归获得当前根节点的左右子树;
  • 最后返回根节点即为平衡的二叉搜索树。
import com.kaesar.leetcode.TreeNode; public class LeetCode_108 { public static TreeNode sortedArrayToBST(int[] nums) { // 调用递归方法,初始的起始位置为数组的长度 return sortedArrayToBST(nums, 0, nums.length - 1); }/** * 递归 * * @param nums * @param left * @param right * @return */ private static TreeNode sortedArrayToBST(int[] nums, int left, int right) { // 当起点位置大于终点位置时,说明节点已经遍历完了,直接返回空树 if (left > right) { return null; } // 获取中间位置的值作为根节点,这样左右子树的节点树是较为平衡点 int mid = (left + right) / 2; TreeNode root = new TreeNode(nums[mid]); // 然后递归获得当前根节点的左右子树 root.left = sortedArrayToBST(nums, left, mid - 1); root.right = sortedArrayToBST(nums, mid + 1, right); return root; }public static void main(String[] args) { int[] nums = new int[]{-10, -3, 0, 5, 9}; sortedArrayToBST(nums).print(); } }

【每日寄语】 不辜负每个朝阳,不荒废每个深夜,因平凡而奋斗,因奋斗而不平凡。

    推荐阅读