- 浏览: 914808 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (537)
- Java SE (114)
- Struts (18)
- Hibernate (25)
- Spring (3)
- Page_Tech (41)
- Others (87)
- Database (29)
- Server (24)
- OpenSource_Tools (15)
- IDE_Tool (22)
- Algorithm (28)
- Interview (22)
- Test (28)
- Hardware (1)
- Mainframe (25)
- Web application (4)
- Linux (3)
- PHP (17)
- Android (1)
- Perl (6)
- ubuntu (1)
- Java EE (9)
- Web Analysis (5)
- Node.js (2)
- javascript (2)
最新评论
-
一键注册:
request.getRequestURL()和request.getRequestURI() -
SuperCustomer:
...
SED的暂存空间和模式空间 -
juyo_ch:
讲得挺好理解的,学习了
java 死锁及解决 -
chinaalex:
最后一题答案正确,但是分析有误.按照如下过程,上一行为瓶,下一 ...
zz智力题 -
liaowuxukong:
多谢博主啦,弱弱的了解了一点。
C++/Java 实现多态的方法(C++)
题目:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入:
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
- };
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 };
分析:尽管我们可能一下子不能理解镜像是什么意思,但上面的例子给我们的直观感觉,就是交换结点的左右子树。我们试着在遍历例子中的二元查找树的同时来交换每个结点的左右子树。遍历时首先访问头结点8,我们交换它的左右子树得到:
8
/ \
10 6
/\ /\
9 11 5 7
我们发现两个结点6和10的左右子树仍然是左结点的值小于右结点的值,我们再试着交换他们的左右子树,得到:
8
/ \
10 6
/\ /\
11 9 7 5
刚好就是要求的输出。
上面的分析印证了我们的直觉:在遍历二元查找树时每访问到一个结点,交换它的左右子树。这种思路用递归不难实现,将遍历二元查找树的代码稍作修改就可以了。参考代码如下:
- ///////////////////////////////////////////////////////////////////////
- // Mirror a BST (swap the left right child of each node) recursively
- // the head of BST in initial call
- ///////////////////////////////////////////////////////////////////////
- void MirrorRecursively(BSTreeNode *pNode)
- {
- if(!pNode)
- return;
- // swap the right and left child sub-tree
- BSTreeNode *pTemp = pNode->m_pLeft;
- pNode->m_pLeft = pNode->m_pRight;
- pNode->m_pRight = pTemp;
- // mirror left child sub-tree if not null
- if(pNode->m_pLeft)
- MirrorRecursively(pNode->m_pLeft);
- // mirror right child sub-tree if not null
- if(pNode->m_pRight)
- MirrorRecursively(pNode->m_pRight);
- }
/////////////////////////////////////////////////////////////////////// // Mirror a BST (swap the left right child of each node) recursively // the head of BST in initial call /////////////////////////////////////////////////////////////////////// void MirrorRecursively(BSTreeNode *pNode) { if(!pNode) return; // swap the right and left child sub-tree BSTreeNode *pTemp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = pTemp; // mirror left child sub-tree if not null if(pNode->m_pLeft) MirrorRecursively(pNode->m_pLeft); // mirror right child sub-tree if not null if(pNode->m_pRight) MirrorRecursively(pNode->m_pRight); }
由于递归的本质是编译器生成了一个函数调用的栈,因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树。如果它有左子树,把它的左子树压入栈中;如果它有右子树,把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。参考代码如下:
- ///////////////////////////////////////////////////////////////////////
- // 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;
- stackTreeNode.push(pTreeHead);
- while(stackTreeNode.size())
- {
- BSTreeNode *pNode = stackTreeNode.top();
- stackTreeNode.pop();
- // swap the right and left child sub-tree
- BSTreeNode *pTemp = pNode->m_pLeft;
- pNode->m_pLeft = pNode->m_pRight;
- pNode->m_pRight = pTemp;
- // push left child sub-tree into stack if not null
- if(pNode->m_pLeft)
- stackTreeNode.push(pNode->m_pLeft);
- // push right child sub-tree into stack if not null
- if(pNode->m_pRight)
- stackTreeNode.push(pNode->m_pRight);
- }
- }
发表评论
-
IGT JAVA Test
2012-06-18 10:18 01. static synchronized vs synch ... -
zz IBM 面试问题
2012-05-30 14:31 9691.JAVA内存回收机制 2.抽象类与接口的区别 3. ... -
面试的准备与发挥
2012-04-26 10:00 872面试是一场智力的较 ... -
栈内存和堆内存
2010-10-21 11:55 794堆:顺序随意栈:先进 ... -
淘宝面试的几个算法题
2010-10-21 11:27 1478一、给你1副扑克牌,你 ... -
程序员面试题精选(18)-用两个栈实现队列
2010-10-18 22:45 1092题目:某队列的声明如下: C++代码 t ... -
程序员面试题精选(17)-把字符串转换成整数
2010-10-18 22:44 1001题目:输入一个表示整 ... -
程序员面试题精选(16)-O(logn)求Fibonacci数列
2010-10-18 22:41 1836题目:定义Fibonacci数列如下: / ... -
程序员面试题精选(15)-含有指针成员的类的拷贝
2010-10-18 22:41 886题目:下面是一个数组类的声明与实现。请分析这个类有什么问题,并 ... -
程序员面试题精选(14)-圆圈中最后剩下的数字
2010-10-18 22:40 1454题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始 ... -
程序员面试题精选(13)-第一个只出现一次的字符
2010-10-18 22:38 913题目:在一个字符串中找到第一个只出现一次的字符。如输入abac ... -
程序员面试题精选(12)-从上往下遍历二元树
2010-10-18 22:37 967题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按 ... -
程序员面试题精选(10)-在排序数组中查找和为给定值的两个数字
2010-10-18 22:33 1030题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两 ... -
程序员面试题精选(09)-查找链表中倒数第k个结点
2010-10-18 22:32 1145题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数 ... -
程序员面试题精选(08)-求1+2+...+n
2010-10-18 22:31 982题目:求1+2+…+n,要求不能使用乘除法、for、while ... -
程序员面试题精选(07)-翻转句子中单词的顺序
2010-10-18 22:30 1175题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺 ... -
程序员面试题精选(06)-判断整数序列是不是二元查找树的后序遍历结果
2010-10-18 22:27 781题目:输入一个整数数 ... -
程序员面试题精选(05)-查找最小的k个元素
2010-10-18 22:24 1441题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3, ... -
程序员面试题精选(04)-在二元树中找出和为某一值的所有路径
2010-10-18 22:22 852题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到 ... -
程序员面试题精选(03)-求子数组的最大和
2010-10-18 22:20 853题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个 ...
相关推荐
《程序员面试题精选100题—何海涛》是一份详实的IT面试准备资料,由何海涛整理发布,旨在帮助应届毕业生和求职者准备面向微软、谷歌等知名科技公司的面试。此资料不仅收录了精选的100道面试题目,还提供了详细的解题...
程序员面试题精选100题 本资源是程序员面试题精选100题,涵盖了算法、数据结构、操作系统、计算机网络、数据库等多个领域。今天,我们将深入分析其中的一道题目,即将二元查找树转换成排序的双向链表。 知识点一:...
java程序员面试题150例 java常见面试题 java工程师面试题 java面试题大全 带搜索功能,能非常方便的查找到你想要了解的 java面试题目 推荐大家下载。
1. **二元查找树(Binary Search Tree, BST)** 二元查找树是一种特殊的树数据结构,其中每个节点包含一个键、一个关联的值、一个指向左子树的引用和一个指向右子树的引用。在二元查找树中,对于任意节点,其左子树...
具体来说,文档中详细讨论了一个在程序员面试中常见的算法问题:如何将二元查找树(Binary Search Tree,BST)转换为一个排序的双向链表。这是一个涉及树的遍历、指针操作、递归思维的经典算法问题。下面将详细介绍...
本文档概述了程序员面试题精选100题,涵盖了C++面试题和笔试题,其中有一道典型的题目是将二元查找树转换成排序的双向链表。 知识点一:二元查找树(Binary Search Tree) * 二元查找树是一种特殊的树数据结构,它...
本资源"程序员面试题精选(1-57)"显然是一个汇集了众多面试题目的集合,涵盖了从基础到高级的各种问题,旨在帮助求职者提升自己的技能并顺利通过面试。 首先,我们要理解数据结构的重要性。数据结构是组织和存储数据...
【程序员考试试题---程序员考试教程】是一系列针对程序员资格认证的考试资料,这些文档主要包含历年的考试试题,旨在帮助备考者熟悉考试形式,提升编程技能和理论知识。程序员考试通常涵盖计算机科学基础,编程语言...
程序员面试宝典 第5版-欧立奇.part2.rar
------------------------------------- java程序员早期面试题汇总 BAT经典面试题汇总.pdf Java常考面试题.pdf java面试题(题库全)....程序员面试题精选100题.pdf ... -------------------------------------
- **二元查找树转双向链表:** 这是一道典型的二叉树操作题目,要求不创建新节点,只调整树中节点的指针,将其转换为排序的双向链表。两种常见的解题思路是: - **递归法1:** 从根节点开始,先处理左子树,将左...
人事面试题150问完整版,附加.NET程序员面试题,所有题目绝对真实有效,欢迎下载!O(∩_∩)O哈哈~
在程序员面试中,数据结构和算法是经常被考察的重要领域,尤其是涉及到二元查找树(Binary Search Tree, BST)的问题。本题目的核心是将一个二元查找树转换成一个排序的双向链表,这涉及到对树结构的深入理解和递归...
1. **二元查找树(Binary Search Tree, BST)** 二元查找树是一种特殊的二叉树,其中每个节点的值都大于其左子树中任何节点的值,小于其右子树中任何节点的值。这种特性使得在二元查找树中进行查找、插入和删除操作...
本题要求将二叉查找树转化为一个排序的双向链表,这一转换不仅考验应聘者对二叉树特性的理解,同时也考察了其对链表操作的熟练程度。 #### 1.2 题目描述 题目要求输入一棵二叉查找树,并将其转换为一个排序的双向...