学步园

题目:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入:
    8
   / \

  6 10
 / \   /\

5 7 9 11
输出:   
    8
   /  \ 
10  6
 /  \  /  \
11 9 7 5

思想：1先交换根节点的左右子树 2交换值为10的节点的左右字节点；3交换值为6的节点的左右字节点

实现方案：

递归实现

void mirro_tree(BTNode *root)
{
	if(root==NULL)
		return ;
	BTNode *temp = root->left;  //交换根节点
	root->left = root->right;
	root->right = temp;
	if(root->left)
		mirro_tree(root->left);
	if(root->right)
		mirro_tree(root->right);
}

非递归实现：

void non_mirro_tree(BTNode *root)
{
	if(root==NULL)
		return ;
	stack<BTNode*> s_node;
	s_node.push(root);
	while(s_node.size())
	{
		BTNode *pNode = s_node.top();
		s_node.pop();
		BTNode *pTmp = pNode->left;
		pNode->left = pNode->right;
		pNode->right = pTmp;
		if(pNode->left)
			s_node.push(pNode->left);
		if(pNode->right)
			s_node.push(pNode->right);
	}
}

(以上为剑指offer读书笔记)