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


将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点   的左右两个子树的高度差的绝对值不超过 1。

示例:
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

0
    /
  -3   9
  /   /
-10  5

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0){
            return null;
        }
        return helper(nums,0,nums.length-1);
    }

    public TreeNode helper(int[] nums,int start,int end) {
        if(start > end){
            return null;
        }else{
            int mid = (start+end)/2;
            TreeNode root = new TreeNode();
            root.val  =nums[mid];
            root.left =helper(nums,start,mid-1);//-1
            root.right=helper(nums,mid+1,end);
            return root;
        }
    }

}

https://cdn.jsdelivr.net/gh/future1314/images@master/img/%E6%88%AA%E5%B1%8F2020-09-15%20%E4%B8%8B%E5%8D%883.31.12.jpg

https://cdn.jsdelivr.net/gh/future1314/images@master/img/%E6%88%AA%E5%B1%8F2020-09-15%20%E4%B8%8B%E5%8D%883.30.49.jpg


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
热爱生命 热爱生命
《热爱生命》   我不去想   是否能够成功   既然选择了远方   便只顾风雨兼程   我不去想   能否赢得爱情   既然钟情于玫瑰   就勇敢地吐露真诚   我不去想   身后会不会袭来寒风冷雨   既然目标是地平线   留给世界
2020-09-23 future
下一篇 
102. 二叉树的层序遍历 102. 二叉树的层序遍历
二叉树的层序遍历给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。 示例:二叉树:[3,9,20,null,null,15,7], 3  /  9  20   /     15   7返回其层次遍
2020-09-13 future
  目录