没有合适的资源?快使用搜索试试~ 我知道了~
首页程序员面试题精选:二叉查找树转排序链表
程序员面试题精选:二叉查找树转排序链表
需积分: 0 1 下载量 49 浏览量
更新于2024-06-17
收藏 11.41MB PDF 举报
"《程序员面试题精选100题》是一份针对求职者编写的面试指南,主要关注于提升面试者在技术领域的竞争力。书中包含了100个精选的编程面试问题,涉及数据结构、算法、系统设计、网络、数据库等多个关键领域,旨在帮助求职者了解和准备常见的面试挑战。 本篇讨论的主题是“二元查找树(Binary Search Tree,BST)转为排序双向链表”这一经典面试题。题目要求将给定的二元查找树转换成一个排序的双向链表,且需在不增加新节点的前提下仅调整指针。这个问题考察的是面试者对递归和中序遍历算法的理解,以及如何利用这些技巧进行树的变形操作。 思路一采用递归策略,首先处理左子树,将其转换为有序链表,然后将左子链表的最右侧节点与当前节点连接,接着调整右子树,最后从根节点开始递归,直到遍历完整棵树。这种递归方法确保了链表的顺序性。 思路二则是通过中序遍历,按照数值大小顺序访问节点,每次访问后将当前节点插入到已排序链表的末尾。这种方式同样实现了链表的排序,但更注重理解链表操作和遍历的逻辑。 在代码实现中,首先定义了一个BSTTreeNode结构体,包含了节点值、左子节点和右子节点的引用。对于思路一的具体实现,函数可能包括判断节点左右子角色的参数,然后递归地处理左右子树,并调整指针链接。思路二的代码则会涉及到遍历函数,使用栈或递归来完成节点的中序遍历。 通过解决这类问题,面试者不仅能展示自己的编程基础和算法理解能力,还能体现对数据结构操作的熟练程度,这对于成功通过技术面试至关重要。在实际面试过程中,解答这类问题时需要清晰的逻辑推理,良好的代码组织能力,以及对时间复杂度和空间复杂度的考量,这些都是评估候选人潜力的重要方面。"
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/88783702/bg10.jpg)
{
char temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
pBegin ++, pEnd --;
}
}
/////////////////////////////////////////////////////////////////////
//
// Reverse the word order in a sentence, but maintain the character
// order inside a word
// Input: pData - the sentence to be reversed
/////////////////////////////////////////////////////////////////////
//
char* ReverseSentence(char *pData)
{
if(pData == NULL)
return NULL;
char *pBegin = pData;
char *pEnd = pData;
while(*pEnd != '\0')
pEnd ++;
pEnd--;
// Reverse the whole sentence
Reverse(pBegin, pEnd);
// Reverse every word in the sentence
pBegin = pEnd = pData;
while(*pBegin != '\0')
{
if(*pBegin == ' ')
{
pBegin ++;
pEnd ++;
continue;
}
// A word is between with pBegin and pEnd, reverse it
else if(*pEnd == ' ' || *pEnd == '\0')
{
![](https://csdnimg.cn/release/download_crawler_static/88783702/bg11.jpg)
Reverse(pBegin, --pEnd);
pBegin = ++pEnd;
}
else
{
pEnd ++;
}
}
return pData;
}
员 试 题 选
程序 面 精 100
题
(08)-求 1+2+...+n
题目:求 1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及条件判断语
句(A?B:C)。
分析:这道题没有多少实际意义,因为在软件开发中不会有这么变态的限制。但这道题却能有效地考查发
散思维能力,而发散思维能力能反映出对编程相关技术理解的深刻程度。
通常求 1+2+…+n 除了用公式 n(n+1)/2 之外,无外乎循环和递归两种思路。由于已经明确限制 for 和 while
的使用,循环已经不能再用了。同样,递归函数也需要用 if 语句或者条件判断语句来判断是继续递归下去
还是终止递归,但现在题目已经不允许使用这两种语句了。
我们仍然围绕循环做文章。循环只是让相同的代码执行 n 遍而已,我们完全可以不用 for 和 while 达到这个
效果。比如定义一个类,我们 new 一含有 n 个这种类型元素的数组,那么该类的构造函数将确定会被调用
n 次。我们可以将需要执行的代码放到构造函数里。如下代码正是基于这个思路:
class Temp
{
public:
Temp() { ++ N; Sum += N; }
static void Reset() { N = 0; Sum = 0; }
static int GetSum() { return Sum; }
private:
static int N;
static int Sum;
};
![](https://csdnimg.cn/release/download_crawler_static/88783702/bg12.jpg)
int Temp::N = 0;
int Temp::Sum = 0;
int solution1_Sum(int n)
{
Temp::Reset();
Temp *a = new Temp[n];
delete []a;
a = 0;
return Temp::GetSum();
}
我们同样也可以围绕递归做文章。既然不能判断是不是应该终止递归,我们不妨定义两个函数。一个函数
充当递归函数的角色,另一个函数处理终止递归的情况,我们需要做的就是在两个函数里二选一。从二选
一我们很自然的想到布尔变量,比如 ture(1)的时候调用第一个函数,false(0)的时候调用第二个函数。
那现在的问题是如和把数值变量 n 转换成布尔值。如果对 n 连续做两次反运算,即!!n,那么非零的 n 转换
为 true,0 转换为 false。有了上述分析,我们再来看下面的代码:
class A;
A* Array[2];
class A
{
public:
virtual int Sum (int n) { return 0; }
};
class B: public A
{
public:
virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }
};
int solution2_Sum(int n)
{
A a;
B b;
Array[0] = &a;
Array[1] = &b;
int value = Array[1]->Sum(n);
![](https://csdnimg.cn/release/download_crawler_static/88783702/bg13.jpg)
return value;
}
这种方法是用虚函数来实现函数的选择。当 n 不为零时,执行函数 B::Sum;当 n 为 0 时,执行 A::Sum。
我们也可以直接用函数指针数组,这样可能还更直接一些:
typedef int (*fun)(int);
int solution3_f1(int i)
{
return 0;
}
int solution3_f2(int i)
{
fun f[2]={solution3_f1, solution3_f2};
return i+f[!!i](i-1);
}
另外我们还可以让编译器帮我们来完成类似于递归的运算,比如如下代码:
template <int n> struct solution4_Sum
{
enum Value { N = solution4_Sum<n - 1>::N + n};
};
template <> struct solution4_Sum<1>
{
enum Value { N = 1};
};
solution4_Sum<100>::N 就是 1+2+...+100 的结果。当编译器看到 solution4_Sum<100>时,
就是为模板类 solution4_Sum 以参数 100 生成该类型的代码。但以 100 为参数的类型需要得到以 99
为参数的类型,因为 solution4_Sum<100>::N=solution4_Sum<99>::N+100。这个过程会
递归一直到参数为 1 的类型,由于该类型已经显式定义,编译器无需生成,递归编译到此结束。由于这个
过程是在编译过程中完成的,因此要求输入 n 必须是在编译期间就能确定,不能动态输入。这是该方法最
大的缺点。而且编译器对递归编译代码的递归深度是有限制的,也就是要求 n 不能太大。
大家还有更多、更巧妙的思路吗?欢迎讨论^_^
PS:递归解决
int func(int n)
{
int i=1;
![](https://csdnimg.cn/release/download_crawler_static/88783702/bg14.jpg)
(n>1)&&(i=func(n-1)+n);
return i;
}
员 试 题 选
程序 面 精 100
题
(09)
查 链 数
- 找 表中倒 第 k
个 结
点
题目:输入一个单向链表,输出该链表中倒数第 k 个结点。链表的倒数第 0 个结点为链表的尾指针。链表
结点定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析:为了得到倒数第 k 个结点,很自然的想法是先走到链表的尾端,再从尾端回溯 k 步。可是输入的是
单向链表,只有从前往后的指针而没有从后往前的指针。因此我们需要打开我们的思路。
既然不能从尾结点开始遍历这个链表,我们还是把思路回到头结点上来。假设整个链表有 n 个结点,那么
倒数第 k 个结点是从头结点开始的第 n-k-1 个结点(从 0 开始计数)。如果我们能够得到链表中结点的个
数 n,那我们只要从头结点开始往后走 n-k-1 步就可以了。如何得到结点数 n?这个不难,只需要从头开始
遍历链表,每经过一个结点,计数器加一就行了。
这种思路的时间复杂度是 O(n),但需要遍历链表两次。第一次得到链表中结点个数 n,第二次得到从头结
点开始的第 n-k-1 个结点即倒数第 k 个结点。
如果链表的结点数不多,这是一种很好的方法。但如果输入的链表的结点个数很多,有可能不能一次性把
整个链表都从硬盘读入物理内存,那么遍历两遍意味着一个结点需要两次从硬盘读入到物理内存。我们知
道把数据从硬盘读入到内存是非常耗时间的操作。我们能不能把链表遍历的次数减少到 1?如果可以,将
能有效地提高代码执行的时间效率。
如果我们在遍历时维持两个指针,第一个指针从链表的头指针开始遍历,在第 k-1 步之前,第二个指针保
持不动;在第 k-1 步开始,第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在 k-1,
当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针正好是倒数第 k 个结
点。
这种思路只需要遍历链表一次。对于很长的链表,只需要把每个结点从硬盘导入到内存一次。因此这一方
法的时间效率前面的方法要高。
思路一的参考代码:
剩余95页未读,继续阅读
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)