Day 20, 88,108, Merge Sorted Array, Convert Sorted Array to Binary Search Tree

Sorted Array
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.
-------------------------------------
 Solution #1, pooooooooooooooor algorithm, O(m*n)?

class Solution {
public:
    void move (int i, int A[], int m) {
        for (int j=m;j>=i;j--) {
            A[j+1] = A[j];
        }
    }
    
    void merge(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int j=0;
        for (int i=0;i<m;i++) {
            if (j<n && A[i] > B[j]) {
                move(i,A,m);
                m++;
                A[i] = B[j];
                j++;
            }
        }
        if (j<n) {
            int length = n-j;
            for (int i=m;i<m+length+1;i++) {
                A[i] = B[j];
                j++;
            }
        }
    }
};

Solution #2, start from the back of two arrays
O(m+n)complexity, no extra space used

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int index = m+n-1;
        int a = m-1;
        int b = n-1;
        for (;index >= 0;index--) {
            if (a>=0 && b>=0 && A[a] > B[b]) {
                A[index] = A[a];
                a--;
            }else if (b>=0) {
                A[index] = B[b];
                b--;
            }
        }
    }
};

Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
------------------------------
recursion, nothing fancy

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *devide (int left, int right, vector<int> &num) {
        int mid = (left+right) / 2;
        TreeNode* root = new TreeNode(num[mid]);
        if (left <= mid-1 )
            root->left = devide(left,mid-1,num); 
        if (right >= mid+1)
            root->right = devide(mid+1,right,num); 
        return root;
    }

    TreeNode *sortedArrayToBST(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (num.size() == 0) return NULL;
        return devide(0,num.size()-1,num);
    }
};

Update on Sep-05-2014
Set up the conditions so one node does not contain itself as its child