leetcode——[108]Convert Sorted Array to Binary Search Tree将有序数组转换为二叉搜索树

题目

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

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

示例:

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

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

      0
     / \
   -3   9
   /   /
 -10  5

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

解题方法

递归构造BST，每次取数组中心位置的节点作为子树的根，第一次写的代码在递归调用时需要防止引用参数丢失，所以调用前需要先对root进行实例化，第二次经过修改不需要注意这点，两段代码跑了1ms，超过100%的Java提交，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // Method_01  1ms  100.00%
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) { //边界判断
            return null;
        }
        TreeNode root = new TreeNode(0);  // 先实例化，防止传递空指针
        subArrayToBST(0, nums.length - 1, root, nums);  // 递归调用
        return root;
    }

    private void subArrayToBST(int start, int end, TreeNode root, int[] nums) {
        int index = (start + end) / 2;  //取中心节点作为父节点
        root.val = nums[index];
        if (start == end){  // 递归结束条件
            return;
        }
        if (start != index) {  // start == index时start > index - 1
            root.left = new TreeNode(0);
            subArrayToBST(start, index - 1, root.left, nums);
        }
        if (index != end) {  // 同上
            root.right = new TreeNode(0);
            subArrayToBST(index + 1, end, root.right, nums);
        }
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // Method_02  1ms  100.00%
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) { //边界判断
            return null;
        }
        return subArrayToBST(0, nums.length - 1, nums);  // 递归调用，直接返回根节点
    }

    private TreeNode subArrayToBST(int start, int end, int[] nums) {
        int index = (start + end) / 2;  //取中心节点作为父节点
        TreeNode root = new TreeNode(nums[index]);
        if (start == end){  // 递归结束条件
            return root;
        }
        if (start != index) {  // start == index时start > index - 1
            root.left = subArrayToBST(start, index - 1, nums);
        }
        if (index != end) {  // 同上
            root.right = subArrayToBST(index + 1, end, nums);
        }
        return root;
    }
}