Java刷题笔记3：将有序数组转换为二叉搜索树

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

题目描述：示例：递归1.0递归2.0

题目描述：

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

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

示例：

题目链接 这个题属于简单难度题。为了使高度平衡，那么对于其任意一个节点的左右子树高度差就不能超过1. 为此，我们可以取出数组中间的元素作为根节点，然后对于左子树则在nums[left:mid-1]中取一中间元素作为节点，右子树则在nums[mid+1:right]之间取中间元素作为节点.因为对于每一个结点，它的左右子树均从数组中取走一半的数，那么我们就可以保证左右两边子树的差值不会超过一。如示例中，先取nums[2]作为root，然后对于其左子树，则在{10}中取中间元素，即root.left.value=nums[0]=-10,root.right则在{5，9}中取一个元素。我们可以选择偏向于右边的元素9。此时root.right.value=9.对于它们各自的左右子树我们可以采取递归的方式来处理

递归1.0

public static TreeNode sortedArrayToBST(int[] nums) { if (nums.length < 1) return null; int mid = nums.length / 2; TreeNode root = new TreeNode(nums[mid]); helper(root, nums, 0, nums.length - 1); return root; } private static void helper(TreeNode root, int[] nums, int start, int end) { if (start == end || start + 1 == end) {//此时只剩下一个元素没处理 if (nums[start] > root.val) { root.right = new TreeNode(nums[start]); } else if (nums[start] < root.val) root.left = new TreeNode(nums[start]); return; } int mid = (end + start + 1) >> 1; int leftMid = (mid + start ) >> 1; int rightMid = (end + mid + 2) >> 1; root.left = new TreeNode(nums[leftMid]); root.right = new TreeNode(nums[rightMid]); helper(root.left, nums, start, mid - 1);//继续处理左子树 helper(root.right, nums, mid + 1, end);//处理右子树 }

上述代码完全按照刚开始的思路来写的，虽然结果正确，相率也很高，但可读性极差。从这里我也认识到了我写递归代码的能力还有待提高。在经过一番改造之后最终写出了让自己满意的代码。核心思想还是对于任意结点，先从数组中取中间元素(偏右 {1,2}我们选择2）.然后对于左右子树继续递归处理

递归2.0

public static TreeNode sortedArrayToBST2(int[] nums) { return helper2(nums,0,nums.length-1); } private static TreeNode helper2(int[] nums, int start, int end) { if (start>end) return null; int mid=(end+start+1)>>1; TreeNode root=new TreeNode(nums[mid]); root.left=helper2(nums,start,mid-1); root.right=helper2(nums,mid+1,end); return root; }

时间复杂读没有变仍然是O(n)。