LeetCode.108.Convert Sorted Array to Binary Search Tree 升序数组转BST

题目描述

108 Convert Sorted Array to Binary Search Tree https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

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 的中序遍历序列就是升序数组。 给定 bst 的中序遍历序列，生成的 bst 是不一定的，最极端的，可以生成一个高度为 n 的单边二叉树。 为了尽可能的使 bst 平衡，可以每次取中间节点作为根，然后递归的生成左右子树。

时间复杂度 O(n)，空间复杂度 O(logn)

SolutionV202001

private static class SolutionV202001 {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (null == nums) {
            return null;
        }
        return sortedArrayToBSTRecursive(nums, 0, nums.length -1 );
    }

    private TreeNode sortedArrayToBSTRecursive(int[] nums, int left ,int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return new TreeNode(nums[left]);
        }
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBSTRecursive(nums, left, mid - 1);
        root.right = sortedArrayToBSTRecursive(nums, mid + 1, right);
        return root;
    }
}

SolutionV202007

和半年前写的代码竟然一模一样。

private static class SolutionV202007 {
    public TreeNode sortedArrayToBST(int[] nums) {
        return toBST(nums, 0, nums.length - 1);
    }

    // 递归的将 nums[left...right] 转换为 bst
    private TreeNode toBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return new TreeNode(nums[left]);
        }
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = toBST(nums, left, mid - 1);
        root.right = toBST(nums, mid + 1, right);
        return root;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_108_ConvertSortedArrayToBinarySearchTree.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_108_ConvertSortedArrayToBinarySearchTree.java