您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

将有序数组转换为二叉搜索树(图文)

第十三双眼睛2023-11-27【数据结构与算法】人已围观

简介将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。
高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

思路：将数组的中间元素当成根节点，然后将中间元素的左边部分数组去构造根节点的左子树，将中间元素的右边部分数组去构造根节点的右子树，里面的逻辑也是一样，因此可以递归实现。代码如下：

public static TreeNode method1(int[] nums) {
   return test(nums, 0, nums.length - 1);
}

public static TreeNode test(int[] nums, int start, int end) {
   if (start > end) {
       return null;
   }
   int mid = (start + end) / 2;
   TreeNode root = new TreeNode(nums[mid]);
   // 构建左子树
   root.left = test(nums, start, mid - 1);
   root.right = test(nums, mid + 1, end);
   return root;
}

Tags：

很赞哦！ ()

上一篇：二叉树的最大深度(图文)

下一篇：平衡二叉树(图文)