[Microsoft面试]题目：输入一颗二元查找树，将该树转换为它的镜像， 即在转换后的二元查找树中，左子树的结点都大于右子树的结点。

用递归和循环两种方法完成树的镜像转换。 要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入：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 nodeBSTreeNode *m_pLeft; // left child of nodeBSTreeNode *m_pRight; // right child of node};

This isthe basic application of recursion.PS: I don’t like the m_xx naming convension.void swap(Node ** l, Node ** r) {  Node * p = *l;  *l = *r;  *r = p;}voidmirror(Node * root) {  if (root == NULL) return;  swap(&(root->left), &(root->right));  mirror(root->left);  mirror(root->right);}voidmirrorIteratively(Node * root) {  if (root == NULL) return;  stack<Node*> buf;  buf.push(root);  while (!stack.empty()) {    Node * n = stack.pop();    swap(&(root->left), &(root->right));    if (root->left != NULL) buf.push(root->left);    if (root->right != NULL) buf.push(root->right);  }}