本文共 869 字,大约阅读时间需要 2 分钟。
完成一个函数,输入一个二叉树,该函数输出它的镜像
二叉树结点的定义如下:
struct BinaryTreeNode{ int m_nvalue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};
树的镜像对很多人来说会是一个新的概念,未必一下子能够想出求树的镜像的方法。为了能够形成直观的印象,我们可以自己画一颗二叉树,然后根据照镜子的经验画出它的镜像。
仔细观察可以发现,这两棵树的根节点相同,但它们的左右两个子节点交换了位置
(1)功能测试(普通的二叉树,二叉树的所有结点都没有左子树或者右子树,只有一个结点的二叉树)
(2)特殊输入测试(二叉树的根节点为NULL指针)
void MirrorRecursively( BinaryTreeNode *pNode ){ if( pNode == NULL) return ; if( pNode->m_pLeft == NULL && pNode->m_pRight == NULL ) return; BinaryTreeNode *pTemp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = pTemp; if( pNode->m_pLeft ) MirrorRecursively( pNode->m_pLeft ); if( pNode->m_pRight ) MirrorRecursively( pNode->m_pRight );}
(1)考察对二叉树的理解。本题实质上是利用树的遍历算法解决问题
(2)考察应聘者的思维能力。树的镜像是一个抽象的概念,应聘者需要在短时间内想清楚求镜像的步骤并转化为代码。应聘者可以画图把抽象的问题形象化,这有助于其快速找到解题思路。