2014
11-18

# LeetCode-Convert Sorted Array to Binary Search Tree[二叉树]

### Convert Sorted Array to Binary Search Tree

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

// LeetCode, Convert Sorted Array to Binary Search Tree
// 分治法，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
TreeNode* sortedArrayToBST (vector<int>& num) {
return sortedArrayToBST(num.begin(), num.end());
}

template<typename RandomAccessIterator>
TreeNode* sortedArrayToBST (RandomAccessIterator first,
RandomAccessIterator last) {
const auto length = distance(first, last);

if (length <= 0) return nullptr;  // 终止条件

// 三方合并
auto mid = first + length / 2;
TreeNode* root = new TreeNode (*mid);
root->left = sortedArrayToBST(first, mid);
root->right = sortedArrayToBST(mid + 1, last);

return root;
}
};


Java代码:

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public static TreeNode sortedArrayToBST(int[] num) {
if(num == null || num.length == 0) return null;
return sortedArrayToBST(num, 0, num.length-1);
}

public static TreeNode sortedArrayToBST(int num[],int start, int end){
if(start > end ) return null;
if(start == end) return new TreeNode(num[start]);
int mid = start + (end-start)/2;
TreeNode root = new TreeNode(num[mid]);
root.left = sortedArrayToBST(num, start, mid-1);
root.right = sortedArrayToBST(num, mid+1, end);
return root;
}
}

1. 如果是像日本这样的国家的话，像路口这样的右转也是在最右边的，而且是要看红绿灯通行的，他们的右转相当于我们的左转。

2. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥