11.求二元查找树的镜像[MirrorOfBST]
【题目】
输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入:
8
/ \
6 10
/\ /\
5 7 9 11
输出:
8
/ \
10 6
/\ /\
11 9 7 5
【递归实现】
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
void Swap(BSTreeNode *left, BSTreeNode *right)
{ BSTreeNode *temp = left; left = right; right = temp; } /////////////////////////////////////////////////////////////////////// // swap the right and left child sub-tree // mirror left child sub-tree if not null // mirror right child sub-tree if not null |
【非递归实现】
由于递归的本质是编译器生成了一个函数调用的栈,因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树。如果它有左子树,把它的左子树压入栈中;如果它有右子树,把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。参考代码如下:
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
///////////////////////////////////////////////////////////////////////
// Mirror a BST (swap the left right child of each node) Iteratively // Input: pTreeHead: the head of BST /////////////////////////////////////////////////////////////////////// void MirrorIteratively(BSTreeNode *pTreeHead) { if(!pTreeHead) return; std::stack<BSTreeNode *> stackTreeNode; while(!stackTreeNode.empty()) // swap the right and left child sub-tree // push left child sub-tree into stack if not null // push right child sub-tree into stack if not null |
【参考】
http://zhedahht.blog.163.com/blog/static/2541117420072159363370/
最新文章
- 解密jQuery内核 DOM操作的核心buildFragment
- MIT 6.828 JOS学习笔记8. Exercise 1.4
- ABAP 加密解密程序
- PHP array_count_values() 函数用于统计数组中所有值出现的次数。
- JAVA基础知识之网络编程——-使用MutilcastSocket实现多点广播
- JDK下sun.net.www.protocol.http.HttpURLConnection类-----Http客户端实现类的实现分析
- rsyslog kill 测试重发例子
- HTML之学习笔记(二)颜色体系
- 新浪SAE快速上手教程
- referrer vs referer
- JAVA学习路线图(一文详解)
- api-gateway实践(13)新服务网关 - 断路保护/熔断机制
- 我为什么放弃使用MyBatis3的Mapper注解
- IDEA阅读Spark源码
- Servlet(九):web.xml文件和server.xml文件
- F#周报2019年第16期
- 关于Newtonsoft.Json,LINQ to JSON的一个小demo
- 【2018.05.10 智能驾驶/汽车电子】AutoSar Database-ARXML及Vector Database-DBC的对比
- CodeCraft-19 and Codeforces Round #537 (Div. 2) 题解
- TraceView工具的使用