【每日一题-17】线索化二叉树与单例模式

将二叉搜索树转换成一个排序的双向链表。提示：要求不能创建任何新的结点，只能调整树中结点指针的指向，也就是left当prev，right当next。--中序线索化的变型。 

struct TreeNode
{
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
};
TreeNode* TreeToList(TreeNode* root)
{
	if (root == NULL)
		return;
	TreeNode* pre = NULL;
	TreeNode* cur = root;
	_TreeToList(root, pre);
	while (cur->left != NULL)
		cur = cur->left;
	return cur;
}
TreeNode* _TreeToList(TreeNode* root, TreeNode* &pre)
{
	if (root == NULL)
		return;
	_TreeToList(root->left, pre);
	root->left = pre;
	if (pre)
		pre->right = root;
	pre = root;
	_TreeToList(root->right, pre);
}

单例模式分类&比较：

懒汉模式：只有在必须要创建对象的时候才去创建对象

饿汉模式：程序一开始就创建对象

懒汉模式：实现相对复杂，安全性比较高

饿汉模式：实现简单，但是在某些特殊的场景下不能确保正确性

懒汉模式代码实现：

class singleton
{
protected:
	singleton()
	{
		pthread_mutex_init(&mutex);
	}
private:
	static singleton* p;
public:
	static pthread_mutex_t mutex;
	static singleton* initance();
};

pthread_mutex_t singleton::mutex;
singleton* singleton::p = NULL;
singleton* singleton::initance()
{
	if (p == NULL)
	{
		pthread_mutex_lock(&mutex);
		if (p == NULL)
			p = new singleton();
		pthread_mutex_unlock(&mutex);
	}
	return p;
}

class singleton
{
protected:
	singleton()
	{}
private:
	static singleton* p;
public:
	static singleton* initance();
};
singleton* singleton::p = new singleton;

singleton* singleton::initance()
{
	return p;
}