题目(二叉树)

1、把一棵二叉树转换为它的镜像树

//  转换成镜像树
void mirror_tree(TreeNode* root)
{
	if(NULL == root)	return;
	
	TreeNode* temp = root->left;
	root->left = root->right;
	root->right = temp;

	mirror_tree(root->left);
	mirror_tree(root->right);
}

2、输入两棵二叉树A、B，判断B是不是A的子结构(我们约定空树不是任意一棵树的子结构)

//  判断两棵树
bool treecmp(TreeNode* r1,TreeNode* r2)
{
	if(NULL == r1 && NULL == r2)	return true;
	if(NULL != r1 && NULL == r2)	return true;
	if(NULL == r1 && NULL != r2)	return false;

	if(r1->data != r2->data)	return false;
	return treecmp(r1->left,r2->left) && treecmp(r1->right,r2->right);
}

//  子结构
bool is_subtree(TreeNode* rootA,TreeNode* rootB)
{
	if(NULL == rootA)	return false;

	if(rootA->data == rootB->data)
	{
		bool flag = treecmp(rootA,rootB);
		if(flag)	return true;
	}
	bool lflag = is_subtree(rootA->left,rootB);
	bool rflag = is_subtree(rootA->right,rootB);
	return lflag || rflag;
}

3、计算出有序二叉树中倒数第k大的数

bool _access_tree(TreeNode* root,size_t index,int* ptr,int* k)
{
	if(NULL == root)	return false;
	bool lflag = _access_tree(root->right,index,ptr,k);
	if((*k)++ == index)
	{
		*ptr = root->data;
		return true;
	}
	bool rflag = _access_tree(root->left,index,ptr,k);
	return lflag || rflag;
}

4、判断一棵二叉树是否是对称

bool _is_sym(TreeNode* root1,TreeNode* root2)
{
	if(NULL == root1 && NULL == root2)	return true;
	if(NULL == root1 && NULL != root2)	return false;
	if(NULL != root1 && NULL == root2)	return false;
	if(root1->data != root2->data)	return false;

	bool lflag = _is_sym(root1->left,root2->right);
	bool rflag = _is_sym(root1->right,root2->left);
	return lflag && rflag;
}

//  对称
bool is_sym(TreeNode* root)
{
	return _is_sym(root->left,root->right);	
}

5、将一棵有序二叉树转换为一个有序的双向循环链表

//  尾添加链表
void __add_tail_list(TreeNode** head,TreeNode* node)
{
	if(NULL == *head)
	{
		*head = node;
	}
	else
	{
		(*head)->left->right = node;
		node->left = (*head)->left;
	}
	(*head)->left = node;
	//node->right = (*head);
}

void _tree_to_list(TreeNode* root,TreeNode** head)
{
	if(NULL == root)	return;
	//  按照中序遍历树，尾添加到链表中
	_tree_to_list(root->left,head);
	__add_tail_list(head,root);
	_tree_to_list(root->right,head);
}

//  有序二叉树转有序双链表
TreeNode* tree_to_list(TreeNode* root)
{
	//  不带头节点的链表
	TreeNode* head = NULL;
	_tree_to_list(root,&head);
	head->left->right = head;
	return head;
}