leetCode-108:Convert Sorted Array to Binary Search Tree

问题描述

给定一个升序的整数数组，要求将其转换成高度平衡的搜索二叉树。题目链接：**点我**

样例输入输出

输入：[-10,-3,0,5,9]

输出：[0,-3,9,-10,null,5]，或，[0,-10,5,null,-3,null,9]

解释：树形状如下

或：

输入：[1]

输出：[1]

问题解法

使用递归，将数组对半分，中间节点为根节点，左边的数组构成左子树，右边的数组构成右子树。代码如下

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return convert2BST(nums, 0, nums.length - 1);
    }
    
    private TreeNode convert2BST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        
        if (start == end) {
            return new TreeNode(nums[start]);
        }
        
        int middle = (start + end) / 2;
        TreeNode root = new TreeNode(nums[middle]);
        root.left = convert2BST(nums, start, middle - 1);
        root.right = convert2BST(nums, middle + 1, end);
        return root;
    }
}