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. // Convert Sorted Array to Binary Search Tree
  2. // 二分法，时间复杂度O(n)，空间复杂度O(logn)
  3. public class Solution {
  4.     public TreeNode sortedArrayToBST (int[] nums) {
  5.         return sortedArrayToBST(nums, 0, nums.length);
  6.     }
  8.     private static TreeNode sortedArrayToBST (int[] nums, int begin, int end) {
  9.         int length = end - begin;
  10.         if (length < 1) return null;  // 终止条件
  12.         // 三方合并
  13.         int mid = begin + length / 2;
  14.         TreeNode root = new TreeNode (nums[mid]);
  15.         root.left = sortedArrayToBST(nums, begin, mid);
  16.         root.right = sortedArrayToBST(nums, mid + 1, end);
  18.         return root;
  19.     }
  20. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/bst/convert-sorted-array-to-binary-search-tree.html