研发埠

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

作者: 陈荣莲 时间: 2013-8-16 10:57
标题: [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};

作者: 秦静静 时间: 2013-8-16 11:10
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); }}

欢迎光临研发埠 (http://bbs.yanfabu.com/)