​​​​​​​​​​​​​LeetCode 108道 .将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

题目示例

示例 1：


输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

  

示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
 

解题思路

选择中间位置左边的数字作为根节点，则根节点的下标为

mid := (start + end) / 2

此处的除法为整数除法。

  • 临界条件是start>end，则中止
  • 左边节点，递归start，mid-1
  • 右边节点，递归mid+1，end
第一种实现-Golang 

type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func TestSortedArrayToBST(t *testing.T){var nums = []int{1,2,3,4,5,6,7,8,9}root:=arrToTreeToBsf(nums,0,len(nums)-1)printfZtree(root)
}func arrToTreeToBsf(nums []int,start,end int) *TreeNode{if start>end{return nil}//取中间位置，用作根节点mid := (start + end) / 2root := &TreeNode{Val: nums[mid]}//左边节点、是从0开始到中间节点root.Left=arrToTreeToBsf(nums,start,mid-1)//右边节点、是从中间节点+1开始到末尾root.Right=arrToTreeToBsf(nums,mid+1,end)return root
}//中序遍历，左根右
func printfZtree( tr *TreeNode)  {if tr==nil{return}printfZtree(tr.Left)fmt.Printf("%v ->",tr.Val)printfZtree(tr.Right)
}
第二种实现-Java 
import java.util.Stack;/*** Definition for a binary tree node.**/
public class SortedArrayToBST {public static void main(String[] args) {int[] a={1,2,3,4,5,6,7,8,9};TreeNode treeNode = sortedArrayToBST(a);System.out.println(" " );printfZtree(treeNode);}//中序遍历，左根右public  static  void printfZtree(TreeNode node){if(node==null){return;}printfZtree(node.left);System.out.print(node.val + "->");printfZtree(node.right);}public static TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums, 0, nums.length-1);}private static TreeNode sortedArrayToBST(int[] nums, int start, int end) {if(start > end)return null;//取中间位置，用作根节点int mid = (start + end) / 2;TreeNode root = new TreeNode(nums[mid]);//左边节点、是从0开始到中间节点-1root.left = sortedArrayToBST(nums, start, mid-1);//右边节点、是从中间节点+1开始到末尾root.right = sortedArrayToBST(nums, mid + 1, end);return root;}public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}}
结果验证

Java结果验证：

 

Golang结果验证：

​​​​​​​