面试题 04.02

Given a sorted (increasing order) array with unique integer elements, write an algo­rithm to create a binary search tree with minimal height.

Example:

Given sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5]，which represents the following tree:

      0 
     / \ 
   -3   9 
   /   / 
 -10  5 

Solutions

1. binary search tree

2. Recursively build the root node with the middle element and link subtrees of two parts as the child nodes.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode * create_bst(vector<int> & nums, int lo, int hi) {
        if (lo >= hi) return nullptr;
        else if (hi - lo == 1)
            return new TreeNode(nums[lo]);
        else {
            int mid = lo + ((hi - lo) >> 1);
            TreeNode * root = new TreeNode(nums[mid]);
            root->left = create_bst(nums, lo, mid);
            root->right = create_bst(nums, mid + 1, hi);
            return root;
        }
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return create_bst(nums, 0, nums.size());
    }
};