二分查找与二叉排序树

二分查找

1.搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int begin = 0;
        int end = nums.size() - 1;
        
        while( begin <= end )
        {
            int mid = (begin + end) / 2;
            if( nums[mid] == target )
            {
                return mid;
            }
            else if( nums[mid] < target )
            {
                begin = mid + 1;
            }
            else
            {
                end = mid - 1;
            }
        }
        
        return begin;
    }
};

2. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result;
        int left = searchLeft(nums, target);
        int right = searchRight(nums, target);
        result.push_back(left);
        result.push_back(right);
        return result;
    }
    
    int searchLeft(vector<int>& nums, int target)
    {
        int begin = 0;
        int end = nums.size() - 1;
        
        while(begin <= end)
        {
            int mid = (begin + end) / 2;
            if( nums[mid] == target )
            {
                if( mid == 0 || nums[mid-1] < nums[mid] )
                {
                    return mid;
                }
                end = mid - 1;
            }
            else if( target < nums[mid] )
            {
                end = mid - 1;
            }
            else
            {
                begin = mid + 1;
            }
        }
        
        return -1;
    }
    
    int searchRight(vector<int>& nums, int target)
    {
        int begin = 0;
        int end = nums.size() - 1;
        
        while(begin <= end)
        {
            int mid = (begin + end) / 2;
            if( nums[mid] == target )
            {
                if( mid == (nums.size() - 1) || nums[mid+1] > nums[mid] )
                {
                    return mid;
                }
                begin = mid + 1;
            }
            else if( target < nums[mid] )
            {
                end = mid - 1;
            }
            else
            {
                begin = mid + 1;
            }
        }
        
        return -1;
    }
};

3. 搜索旋转排序数组

二叉查找树

4. 序列化和反序列化二叉搜索树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string result = "";
        preOrder(root, result);
        return result;
    }
    
    void preOrder(TreeNode* node, string& str)
    {
        if( !node )
        {
            return ;
        }
        string temp = "";
        int_to_string(node->val, temp);
        str += temp;
        preOrder(node->left, str);
        preOrder(node->right, str);
    }
    
    void int_to_string(int value, string& str)      // 整形转字符型
    {
        string temp = "";
        while(value)
        {
            temp += value % 10 + '0';
            value /= 10;
        }
        
        for(int i=temp.length()-1; i>=0; --i)
        {
            str += temp[i];
        }
        
        str += '#';
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if( data.length() == 0 )
        {
            return NULL;
        }
        
        vector<TreeNode*> vec_tree;
        
        int value = 0;
        for(int i=0; i<data.length(); ++i)
        {
            if( data[i] == '#' )                            // 拆分字符串
            {
                vec_tree.push_back(new TreeNode(value));
                value = 0;
            }
            else                                            // 字符串转数字
            {
                value = value*10 + (data[i] - '0');
            }
        }
        
        for(int i=1; i<vec_tree.size(); ++i)                // 构建二叉搜索树
        {
            BST(vec_tree[0], vec_tree[i]);
        }
        
        return vec_tree[0];
    }
    
    void BST(TreeNode* node, TreeNode* insert_node)         // 二叉搜索树的插入
    {        
        if( insert_node->val < node->val)
        {
            if( node->left )
            {
                BST(node->left, insert_node);
            }
            else
            {
                node->left = insert_node;
            }
        }
        else
        {
            if( node->right )
            {
                BST(node->right, insert_node);
            }
            else
            {
                node->right = insert_node;
            }
        }
    }

};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

5.计算右侧小于当前元素的个数

class Solution {

struct BSTNode
{
    int val;            
    int count;          // 统计左结点的个数
    BSTNode* left;
    BSTNode* right;
    BSTNode(int value) : val(value), count(0), left(NULL), right(NULL) {}
};
    
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> result;        
        vector<BSTNode*> bst;       // 构建的bst树
        vector<int> count;
        
        if( nums.size() == 0 )
        {
            return result;
        }
        
        for(int i=nums.size()-1; i>=0; --i)     // 初始化bst树
        {        
            bst.push_back(new BSTNode(nums[i]));
        }
        
        count.push_back(0);
        for(int i=1; i<bst.size(); ++i)
        {
            int count_small = 0;
            bst_insert(bst[0], bst[i], count_small);
            count.push_back(count_small);
        }
        
        for(int i=count.size()-1; i>=0; --i)
        {
            result.push_back(count[i]);
            delete bst[i];
        }
        
        return result;
    }
    
    void bst_insert(BSTNode* node, BSTNode* insert_node, int& count)
    {
        if( insert_node->val <= node->val )
        {
            node->count++;
            if( node->left )
            {
                bst_insert(node->left, insert_node, count);
            }
            else
            {
                node->left = insert_node;
            }
        }
        else
        {
            count += node->count + 1;
            if( node->right )
            {
                bst_insert(node->right, insert_node, count);
            }
            else
            {
                node->right = insert_node;
            }
        }
    }
};