LintCode 1359: Convert Sorted Array to Binary Search Tree

1359 · Convert Sorted Array to Binary Search Tree
Algorithms
Easy

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example
Example 1:

Input: [-10,-3,0,5,9]
Output: [0,-3,9,-10,#,5]
Explanation:
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/
-3 9
/ /
-10 5

For this tree, you function need to return a tree node which value equals 0.
Example 2:

Input: [1,3]
Output: [3,1]
Explanation:
One possible answer is: [3,1], which represents the following height balanced BST:
3
/
1

For this tree, you function need to return a tree node which value equals 3.
Tags
Company
Airbnb

解法1：递归

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param nums: the sorted array
     * @return: the root of the tree
     */
    TreeNode* convertSortedArraytoBinarySearchTree(vector<int> &nums) {
        int len = nums.size();
        return helper(nums, 0, len - 1);
    }
private:
    TreeNode *helper(vector<int> &nums, int start, int end) {
        if (start > end) return nullptr;
        int mid = start + (end - start) / 2;
        TreeNode *root = new TreeNode(nums[mid]);
        root->left = helper(nums, start, mid - 1);
        root->right = helper(nums, mid + 1, end);
        return root;
    }
};
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
27
28
29
30
31
32
33