题目:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入:
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读书笔记)