[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);}}
页:
[1]