求二元查找树树的镜像(剑指offer笔记)
输入一颗二元查找树,将该树转换为它的镜像
用递归和循环两种方法完成树的镜像转换。
例如输入:
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读书笔记)
