剑指Offer - 面试题27:二叉树的镜像

简介: 剑指Offer - 面试题27:二叉树的镜像

题目

请完成一个函数,输入一棵二叉树,该函数输出它的镜像。二叉树节点的定义如下:


typedef int TElemType;  /* 树结点的数据类型,目前暂定为整型 */
struct BianryTreeNode
{
  TElemType m_nValue;
  BianryTreeNode* m_pLeft, * m_pRight;//左右孩子节点
};

分析

先画出一对二叉树,并写出三序列遍历结果,一会用于判断新的二叉树是否为原二叉树的镜像。观察下图,发现就是左右对调,本质就是依次交换该节点的左右子节点遇到空为止。


递归法

C++

#include <iostream>
using namespace std;
typedef int TElemType;  /* 树结点的数据类型,目前暂定为整型 */
struct BinaryTreeNode
{
  TElemType m_nValue;
  BinaryTreeNode* m_pLeft, * m_pRight;//左右孩子节点
};
void CreatTree(BinaryTreeNode** T)
{
  TElemType elem;
  cin >> elem;
  if (elem != 999)
  {
    *T = new BinaryTreeNode();
    if (NULL == T)
    {
      return;
    }
    (*T)->m_nValue = elem;
    CreatTree(&((*T)->m_pLeft));
    CreatTree(&((*T)->m_pRight));
  }
  else
  {
    *T = nullptr;
  }
}
void Print(TElemType n)
{
  cout << n << " ";
}
void Preorder(BinaryTreeNode* root)//前序遍历
{
  if (NULL == root)
  {
    return;
  }
  Print(root->m_nValue);
  Preorder(root->m_pLeft);
  Preorder(root->m_pRight);
}
void Inorder(BinaryTreeNode* root)//中序输出
{
  if (NULL == root)
  {
    return;
  }
  Inorder(root->m_pLeft);
  Print(root->m_nValue);
  Inorder(root->m_pRight);
}
void Postorder(BinaryTreeNode* root)//后续输出
{
  if (NULL == root)
  {
    return;
  }
  Postorder(root->m_pLeft);
  Postorder(root->m_pRight);
  Print(root->m_nValue);
}
void MirrorRecursively(BinaryTreeNode* pNode)//二叉树的镜像
{
  //当前节点为空,或者没有子树了。
  if ((nullptr == pNode) || (nullptr == pNode->m_pLeft && nullptr == pNode->m_pRight))
  {
    return;
  }
  //交换左右子树
  BinaryTreeNode* tmp = pNode->m_pLeft;
  pNode->m_pLeft = pNode->m_pRight;
  pNode->m_pRight = tmp;
  //调用自己的左子树
  MirrorRecursively(pNode->m_pLeft);
  //调用自己的右子树
  MirrorRecursively(pNode->m_pRight);
}
int main()
{
  BinaryTreeNode* root = nullptr;
  cout << "请按照先序遍历规则输入节点值(输入999表示当前为空):" << endl;
  CreatTree(&root);
  printf("先序输出:");
  Preorder(root);
  printf("\n中序输出:");
  Inorder(root);
  printf("\n后序输出:");
  Postorder(root);
  MirrorRecursively(root);
  cout << "\n--------------二叉树的镜像---------" << endl;
  printf("先序输出:");
  Preorder(root);
  printf("\n中序输出:");
  Inorder(root);
  printf("\n后序输出:");
  Postorder(root);
}


测试结果如下,与上图对比发现完全一致。

本章完!

目录
相关文章
|
26天前
|
算法
二叉树面试题
本文介绍了二叉树相关的几个经典算法问题。首先讲解了如何判断两棵树是否完全相同(LeetCode 100),并给出了代码示例。接着讨论了如何判断一棵树是否是另一棵树的子树(LeetCode 572),详细分析了子树的定义及判断方法。然后介绍了翻转二叉树(LeetCode 226)的实现方法,即在遍历时交换每个节点的左右子树。随后探讨了如何判断一棵树是否是对称的(LeetCode 101),通过对左右子树的递归比较来实现。最后分析了平衡二叉树的概念(LeetCode 110)及判断方法,并给出了优化后的代码示例。此外,还简要介绍了二叉树遍历及二叉树最近公共祖先(LeetCode 236)的问题
19 6
二叉树面试题
|
2月前
|
安全 编译器 C++
【剑指offer】2.2编程语言(p22-p25)——面试题1:string赋值运算函数
【剑指offer】2.2编程语言(p22-p25)——面试题1:string赋值运算函数
|
5月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
5月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
5月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
5月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
5月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
5月前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
2月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
|
2天前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
13 2