第十五题(二元查找树镜像翻转)

2024-08-29 17:58

本文主要是介绍第十五题(二元查找树镜像翻转),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

微软面试100题第十五题

题目:输入一颗二元查找树,将该树转换为它的镜像,

即在转换后的二元查找树中,左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入:
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 node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node

};

采用前序遍历,代码:

namespace MS100P_15
{struct BinaryTreeNode // a node in the binary tree{int m_nValue; // value of nodeBinaryTreeNode *m_pLeft; // left child of nodeBinaryTreeNode *m_pRight; // right child of node};void mirrorSwitch(BinaryTreeNode *root){if (root != NULL){BinaryTreeNode* pTemp;pTemp = root->m_pLeft;root->m_pLeft = root->m_pRight;root->m_pRight = pTemp;mirrorSwitch(root->m_pLeft);mirrorSwitch(root->m_pRight);}}void mirrorSwitch_NonRecursive(BinaryTreeNode*root){stack<BinaryTreeNode*> stck;BinaryTreeNode* p;p = root;while (p != NULL || !stck.empty()){while (p != NULL){BinaryTreeNode* pTemp;pTemp = p->m_pLeft;p->m_pLeft = p->m_pRight;p->m_pRight = pTemp;stck.push(p);p = p->m_pLeft;}if (!stck.empty()){p = stck.top();stck.pop();p = p->m_pRight;}}}}



这篇关于第十五题(二元查找树镜像翻转)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1118567

相关文章

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

C#实现查找并删除PDF中的空白页面

《C#实现查找并删除PDF中的空白页面》PDF文件中的空白页并不少见,因为它们有可能是作者有意留下的,也有可能是在处理文档时不小心添加的,下面我们来看看如何使用Spire.PDFfor.NET通过C#... 目录安装 Spire.PDF for .NETC# 查找并删除 PDF 文档中的空白页C# 添加与删

Docker安装MySQL镜像的详细步骤(适合新手小白)

《Docker安装MySQL镜像的详细步骤(适合新手小白)》本文详细介绍了如何在Ubuntu环境下使用Docker安装MySQL5.7版本,包括从官网拉取镜像、配置MySQL容器、设置权限及内网部署,... 目录前言安装1.访问docker镜像仓库官网2.找到对应的版本,复制右侧的命令即可3.查看镜像4.启

Gradle在国内配置镜像加速的实现步骤

《Gradle在国内配置镜像加速的实现步骤》在国内使用Gradle构建项目时,最大的痛点就是依赖下载贼慢,甚至卡死,下面教你如何配置国内镜像加速Gradle下载依赖,主要是通过改写repositori... 目录引言一、修改 build.gradle 或 settings.gradle 的 reposito

Android Studio 配置国内镜像源的实现步骤

《AndroidStudio配置国内镜像源的实现步骤》本文主要介绍了AndroidStudio配置国内镜像源的实现步骤,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、修改 hosts,解决 SDK 下载失败的问题二、修改 gradle 地址,解决 gradle

Docker镜像修改hosts及dockerfile修改hosts文件的实现方式

《Docker镜像修改hosts及dockerfile修改hosts文件的实现方式》:本文主要介绍Docker镜像修改hosts及dockerfile修改hosts文件的实现方式,具有很好的参考价... 目录docker镜像修改hosts及dockerfile修改hosts文件准备 dockerfile 文

Docker镜像pull失败两种解决办法小结

《Docker镜像pull失败两种解决办法小结》有时候我们在拉取Docker镜像的过程中会遇到一些问题,:本文主要介绍Docker镜像pull失败两种解决办法的相关资料,文中通过代码介绍的非常详细... 目录docker 镜像 pull 失败解决办法1DrQwWCocker 镜像 pull 失败解决方法2总

使用国内镜像源优化pip install下载的方法步骤

《使用国内镜像源优化pipinstall下载的方法步骤》在Python开发中,pip是一个不可或缺的工具,用于安装和管理Python包,然而,由于默认的PyPI服务器位于国外,国内用户在安装依赖时可... 目录引言1. 为什么需要国内镜像源?2. 常用的国内镜像源3. 临时使用国内镜像源4. 永久配置国内镜

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python使用国内镜像加速pip安装的方法讲解

《Python使用国内镜像加速pip安装的方法讲解》在Python开发中,pip是一个非常重要的工具,用于安装和管理Python的第三方库,然而,在国内使用pip安装依赖时,往往会因为网络问题而导致速... 目录一、pip 工具简介1. 什么是 pip?2. 什么是 -i 参数?二、国内镜像源的选择三、如何