package com.q0108;

import com.q0101_symmetric_tree.TreeNode;

/**

* @author xjn

* @since 2020-02-16

* https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

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

* 时间复杂度O(n)

* 空间复杂度O(logN)

*/

public class Solution {

public TreeNode sortedArrayToBST(int[] nums) {

return sortedArrayToBST(nums, 0, nums.length - 1);

}

private TreeNode sortedArrayToBST(int[] nums, int l, int r) {

if (nums == null) {

return null;

}

if (l > r) {

return null;

}

int mid = l + (r - l + 1) / 2;

TreeNode root = new TreeNode(nums[mid]);

TreeNode left = sortedArrayToBST(nums, l, mid - 1);

TreeNode right = sortedArrayToBST(nums, mid + 1, r);

root.left = left;

root.right = right;

return root;

}

public static void main(String[] args) {

}

}