第十五题（二元查找树镜像翻转）

本文主要是介绍第十五题（二元查找树镜像翻转），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

微软面试100题第十五题

题目：输入一颗二元查找树，将该树转换为它的镜像，

即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
8
/ \
6 10
/\ /\
5 7 9 11
输出：
8
/ \
10 6
/\ /\
11 9 7 5
定义二元查找树的结点为：
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node

};

采用前序遍历，代码：

namespace MS100P_15
{struct BinaryTreeNode // a node in the binary tree{int m_nValue; // value of nodeBinaryTreeNode *m_pLeft; // left child of nodeBinaryTreeNode *m_pRight; // right child of node};void mirrorSwitch(BinaryTreeNode *root){if (root != NULL){BinaryTreeNode* pTemp;pTemp = root->m_pLeft;root->m_pLeft = root->m_pRight;root->m_pRight = pTemp;mirrorSwitch(root->m_pLeft);mirrorSwitch(root->m_pRight);}}void mirrorSwitch_NonRecursive(BinaryTreeNode*root){stack<BinaryTreeNode*> stck;BinaryTreeNode* p;p = root;while (p != NULL || !stck.empty()){while (p != NULL){BinaryTreeNode* pTemp;pTemp = p->m_pLeft;p->m_pLeft = p->m_pRight;p->m_pRight = pTemp;stck.push(p);p = p->m_pLeft;}if (!stck.empty()){p = stck.top();stck.pop();p = p->m_pRight;}}}}

这篇关于第十五题（二元查找树镜像翻转）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---