您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
将有序数组转换为二叉搜索树(图文)
第十三双眼睛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:
很赞哦! ()
上一篇:二叉树的最大深度(图文)
下一篇:平衡二叉树(图文)