问题描述:请完成一个函数,输入一个二叉树,该函数输出它的镜像
二叉树定义如下:
struct BinaryTreeNode
{
int value;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
这个问题很直观,一般很快就会有思路:要求树的镜像,我们先前序遍历这棵树的每个结点,如果遍历到的结点有子结点,就交换它的两个子结点。当交换完所有非叶子结点的左右结点之后,就得到了数的镜像。
参考代码如下:
void MirrorRecursively(BinaryTreeNode *pNode) { if((pNode == NULL) || (pNode->m_pLeft == NULL && pNode->m_pRight)) 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); }
上面的代码是用递归实现的,看起来很直观,容易理解。下面我们用迭代的方法来实现,代码如下
void MirrorIteratively(BinaryTreeNode* pRoot) { if(pRoot == NULL) return; std::stack<BinaryTreeNode*> stackTreeNode; stackTreeNode.push(pRoot); while(stackTreeNode.size() > 0) { BinaryTreeNode *pNode = stackTreeNode.top(); stackTreeNode.pop(); BinaryTreeNode *pTemp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = pTemp; if(pNode->m_pLeft) stackTreeNode.push(pNode->m_pLeft); if(pNode->m_pRight) stackTreeNode.push(pNode->m_pRight); } }