导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-108.Convert Sorted Array to Binary Search Tree

题目

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

翻译

给出一个升序数组,将其转换为一颗平衡的二叉搜索树。

每次二分取中点作为根,两侧元素递归。注意二分的终止情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) return null;
return getBalancedBST(nums, 0, nums.length - 1);
}

public TreeNode getBalancedBST(int[] nums, int low, int high) {
if (low > high) return null;
if (low == high) return new TreeNode(nums[low]);

int mid = (high + low) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = getBalancedBST(nums, low, mid - 1);
root.right = getBalancedBST(nums, mid + 1, high);
return root;
}
}