本文共 1637 字，大约阅读时间需要 5 分钟。

• 编程是为了让程序变成自己喜欢的模样！
• 坚持总结经验才是王道
• 代码的样子决定了你的能力！

题目：完成一个函数，输入一颗二叉树、该函数输出它的镜像。

• 二叉树定义如下：

struct BinaryTreeNode{    int 		       m_nValue;    BinaryTreeNode*   m_left;    BinaryTreeNode*   m_right;}

• 输入描述：
  源二叉树：
  

镜像二叉树：

思路： 在做题时大可以画图，在画图的过程中找到规律！！！

先序遍历这棵树的每个结点，如果遍历到的结点有子节点，则交换它的两个子节点。当交换完所有非叶子节点时，就得到了树的镜像！！！！！！！

• 递归实现二叉树镜像，先序遍历！
  代码：

/**    考察面试者将问题通过画图抽象成思路实现代码的能力；    遍历并交换所有非叶子节点的左、右子节点。*/void MirrorRecursively(BinaryTreeNode* pNode){    if(pNode == nullptr)    {        return;    }    if(pNode->m_left == nullptr && pNode->m_right == nullptr)    {        return;    }    // exchange the two children    BinaryTreeNode* temp = pNode->m_left;    pNode->m_left = pNode->m_right;    pNode->m_right = temp;    // continue recursive the two child!    if(pNode->m_left)    {        MirrorRecursively(pNode->m_left);    }    if(pNode->m_right)    {        MirrorRecursively(pNode->m_right);    }}

方法二：

• 既然先序遍历可以用递归实现，也可以用循环迭代实现！！！
• 所用数据结构 栈！！！

代码：

void  MirrorCirculate(BinaryTreeNode* root){    if(root == nullptr)        return;    stack
   
     stackTreeNode;    stackTreeNode.push(root);    while(!stackTreeNode.empty())    {        BinaryTreeNode * parent = stackTreeNode.top();        stackTreeNode.pop();        BinaryTreeNode* temp = parent->m_left;        parent->m_left = parent->m_right;        parent->m_right = temp;        if(parent->m_left)        {            stackTreeNode.push(parent->m_left);        }        if(parent->m_right)        {            stackTreeNode.push(parent->m_right);        }    }}
   

功能呢测试分五种情况

1. 测试完全二叉树：除了叶子节点，其他节点都有两个子节点
2. 测试二叉树：出叶子结点之外，左右的结点都有且只有一个左子结点
3. 测试二叉树：出叶子结点之外，左右的结点都有且只有一个右子结点
4. 测试空二叉树：根结点为空指针
5. 测试只有一个结点的二叉树

转载地址：http://tuzjn.baihongyu.com/