LeetCode Convert Sorted Array to Binary Search Tree

1.题目

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

2.解决方案1

 struct Node{
     TreeNode* t;
     int l;
     int r;
     Node(vector<int> &num, int l, int r){
         this->t = new TreeNode(num[l+(r-l)/2]);
         this->l = l;
         this->r = r;
     }

     Node* getLeft(vector<int> &num){
         int m = l + (r-l)/2;
         if(l>=m) return NULL;
         Node* left = new Node(num, l, m);
         t->left = left->t;
         return left;
     }

     Node* getRight(vector<int> &num){
         int m = l + (r-l)/2;
         if(m+1>=r) return NULL;
         Node* right = new Node(num, m+1, r);
         t->right = right->t;
         return right;
     }
 };

class Solution {
public:

    TreeNode *sortedArrayToBST(vector<int> &num) {
        if(num.size()==0) return NULL;
        stack<Node*> s;
        Node* root = new Node(num, 0, num.size());
        s.push(root);
        while(!s.empty()){
            Node* n = s.top(); s.pop();

            Node* left = n->getLeft(num);
            if(left) s.push(left);

            Node* right = n->getRight(num);
            if(right) s.push(right);
        }
        return root->t;
    }
};

思路:把一个已经排好序的数组转换成一个平衡二叉搜索树。因为是平衡的二叉搜索树，即左右树的高度只相差1.所以对数组进行二分查找，这样找出的数才好建立树。非递归的方式要用到一个stack作为铺助，把所有的点都处理一次，树就建立好了。

3.解决方案2

class Solution {
public:

    TreeNode* build(vector<int> &num, int left, int right){
	if(left <= right){
		int mid = (left + right) / 2;
		TreeNode* rootNode = new TreeNode(num[mid]);
		rootNode->left = build(num,left,mid - 1);
		rootNode->right = build(num,mid + 1, right);
		return rootNode;
	}else{
		return NULL;
	}

}

    TreeNode *sortedArrayToBST(vector<int> &num) {
        int len = num.size();
	TreeNode * root = NULL;
	if(len>0)
		root = build(num, 0, len-1);
	return root;
    }
};

思路:递归建立树是比较常用的方法，但速度非常慢。

http://www.waitingfy.com/archives/1605

数据结构 & 算法 | RSS 2.0 |