leetcode 精选top面试题

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

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

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

示例:

思路参考：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/jiang-you-xu-shu-zu-zhuan-huan-wei-er-cha-sou-s-33/

思路一：中序遍历，总是选择中间位置左边的数字作为根节点

数组中间位置左边元素为根, 递归将左边元素建为左子树，递归将右边元素建为右子树

int mid = left + (right - left) / 2;　　// 向下取整，取得的是中间位置左边的元素

 1 class Solution {
 2 
 3     // 数组中间左边的元素为根, 左边元素为左子树，右边元素为右子树
 4     public TreeNode buildTree(int[] nums, int left, int right){
 5         if(left > right){
 6             return null;
 7         }
 8         int mid = left + (right - left) / 2;　　// 向下取整，取得的是中间位置左边的元素
 9         TreeNode root = new TreeNode(nums[mid]);
10         root.left = buildTree(nums, left, mid - 1);
11         root.right = buildTree(nums, mid + 1, right);
12         return root;
13     }
14 
15     public TreeNode sortedArrayToBST(int[] nums) {
16         return buildTree(nums, 0, nums.length - 1);
17     }
18 }

leetcode 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38.3 MB, 在所有 Java 提交中击败了86.66%的用户

复杂度分析：

时间复杂度：O(n)。遍历了整个数组，所以时间复杂度为O(n)。

空间复杂度：O(logn)。取决于递归栈的深度，因为建成的树是一棵平衡二叉树，所以树的深度为O(logn)，所以空间复杂度为O(logn)。

思路二：中序遍历，总是选择中间位置的数字作为根节点

思路和思路一一样，只不过这次总是选择中间位置的数字作为根节点，因为建出的平衡二叉树可能有多种形态。

int mid = left + (right - left + 1) / 2;　　// 向下取整，取得的是中间位置的元素

 1 class Solution {
 2 
 3     // 数组中间元素为根, 左边元素为左子树，右边元素为右子树
 4     public TreeNode buildTree(int[] nums, int left, int right){
 5         if(left > right){
 6             return null;
 7         }
 8         int mid = left + (right - left + 1) / 2;
 9         TreeNode root = new TreeNode(nums[mid]);
10         root.left = buildTree(nums, left, mid - 1);
11         root.right = buildTree(nums, mid + 1, right);
12         return root;
13     }
14 
15     public TreeNode sortedArrayToBST(int[] nums) {
16         return buildTree(nums, 0, nums.length - 1);
17     }
18 }

leetcode 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38.3 MB, 在所有 Java 提交中击败了86.66%的用户

复杂度分析：

时间复杂度：O(n)。遍历了整个数组，所以时间复杂度为O(n)。

空间复杂度：O(logn)。取决于递归栈的深度，因为建成的树是一棵平衡二叉树，所以树的深度为O(logn)，所以空间复杂度为O(logn)。

思路三：中序遍历，选择任意一个中间位置数字作为根节点

思路和思路一一样，只不过这次总是选择中间位置的数字作为根节点，因为建出的平衡二叉树可能有多种形态。

mid = left + (right - left ) / 2; 或者 mid = left + (right - left + 1) / 2

 1 class Solution {
 2 
 3     // 数组中间元素为根, 左边元素为左子树，右边元素为右子树
 4     public TreeNode buildTree(int[] nums, int left, int right){
 5         if(left > right){
 6             return null;
 7         }
 8         int mid = left + (right - left + new Random().nextInt(2)) / 2;
 9         TreeNode root = new TreeNode(nums[mid]);
10         root.left = buildTree(nums, left, mid - 1);
11         root.right = buildTree(nums, mid + 1, right);
12         return root;
13     }
14 
15     public TreeNode sortedArrayToBST(int[] nums) {
16         return buildTree(nums, 0, nums.length - 1);
17     }
18 }

执行用时：2 ms, 在所有 Java 提交中击败了6.30%的用户, 这里主要是创建 Random对象产生了开销

内存消耗：38 MB, 在所有 Java 提交中击败了95.33%的用户

复杂度分析：

时间复杂度：O(n)。遍历了整个数组，所以时间复杂度为O(n)。

空间复杂度：O(logn)。取决于递归栈的深度，因为建成的树是一棵平衡二叉树，所以树的深度为O(logn)，所以空间复杂度为O(logn)。