二元查找树转排序双向链表的编程面试题解析

需积分: 10 47 浏览量更新于2024-07-29 收藏 643KB PDF 举报

"这是一份2011年的程序员面试题集，包含了100道题目，其中有一道关于将二元查找树转化为排序双向链表的问题。这道题目要求在不创建新节点的情况下，通过调整二元查找树中节点的指针关系，将其转换成有序的双向链表。微软曾经在面试中使用过此题。提供了两种不同的递归思路以及对应的C++代码实现。" 在这篇资源中，主要涉及的知识点包括： 1. **二元查找树 (Binary Search Tree, BST)**: 二元查找树是一种特殊的二叉树，每个节点的左子树只包含比它小的节点，而右子树包含比它大的节点。这种特性使得在树中进行查找、插入和删除操作非常高效。 2. **排序双向链表**: 双向链表是一种链式存储结构，每个节点包含数据和两个指针，分别指向前一个节点和后一个节点。如果链表中的元素按顺序排列，就构成了排序双向链表。 3. **递归算法**: 在解决二元查找树转双向链表问题时，两种思路都采用了递归方法。递归是解决问题的一种常用技巧，通过函数调用自身来解决复杂问题，通常涉及分治策略。 4. **思路一**: - **自底向上递归**：从树的叶子节点开始，逐层调整节点，先处理左子树，然后处理右子树，最后连接左右子树的边界节点。 - 这种方法的关键在于找到每个子树的最小和最大节点，将它们链接起来。 5. **思路二**: - **中序遍历**：二元查找树的中序遍历会得到有序序列。因此，可以按照中序遍历的顺序，依次调整节点的指针，将新访问的节点链接到已形成的链表末尾。 6. **C++代码实现**: - 定义二元查找树节点结构体 `BSTreeNode`，包含值、左孩子和右孩子的指针。 - 提供了思路一的代码实现，`ConvertAsSubBinarySearchTreeIntoASortedDoubleLinkedList` 函数用于转换子树，根据参数 `asRight` 决定返回最大节点还是最小节点。这些知识点对于程序员面试，特别是数据结构和算法部分非常重要。理解并能灵活运用二元查找树和递归算法是提升编程能力的关键。同时，掌握如何将数据结构从一种形式转换为另一种形式的能力，是解决实际问题时的必备技能。

中国程序员社区总结 2011 年

};

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);

中国程序员社区总结 2011 年

};

分析：为了得到倒数第 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 个结点。

这种思路只需要遍历链表一次。对于很长的链表，只需要把每个结点从硬盘导入到内存一次。

因此这一方法的时间效率前面的方法要高。

思路一的参考代码：

/////////////////////////////////////////////////////////////////////

// Find the kth node from the tail of a list

// Input: pListHead - the head of list

// k - the distance to the tail

// Output: the kth node from the tail of a list

/////////////////////////////////////////////////////////////////////

ListNode* FindKthToTail_Solution1(ListNode* pListHead, unsigned int k)

{

if(pListHead == NULL)

return NULL;

// count the nodes number in the list

ListNode *pCur = pListHead;

unsigned int nNum = 0;

while(pCur->m_pNext != NULL)

{

pCur = pCur->m_pNext;

nNum ++;

}

// if the number of nodes in the list is less than k

中国程序员社区总结 2011 年

// when pAhead arrives at the tail, p

// Behind is at the kth node from the tail

while(pAhead->m_pNext != NULL)

{

pAhead = pAhead->m_pNext;

pBehind = pBehind->m_pNext;

}

return pBehind;

}

讨论：这道题的代码有大量的指针操作。在软件开发中，错误的指针操作是大部分问题的根

源。因此每个公司都希望程序员在操作指针时有良好的习惯，比如使用指针之前判断是不是

空指针。这些都是编程的细节，但如果这些细节把握得不好，很有可能就会和心仪的公司失

之交臂。

另外，这两种思路对应的代码都含有循环。含有循环的代码经常出的问题是在循环结束条件

的判断。是该用小于还是小于等于？是该用 k 还是该用 k-1？由于题目要求的是从 0 开始计

数，而我们的习惯思维是从 1 开始计数，因此首先要想好这些边界条件再开始编写代码，

再者要在编写完代码之后再用边界值、边界值减 1、边界值加 1 都运行一次（在纸上写代码

就只能在心里运行了）。

扩展：和这道题类似的题目还有：输入一个单向链表。如果该链表的结点数为奇数，输出中

间的结点；如果链表结点数为偶数，输出中间两个结点前面的一个。如果各位感兴趣，请自

己分析并编写代码。

(10)－在排序数组中查找和为给定值的两个数字

题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和

正好是输入的那个数字。要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字，

输出任意一对即可。

例如输入数组 1、2、4、7、11、15 和数字 15。由于 4+11=15，因此输出 4 和 11。

分析：如果我们不考虑时间复杂度，最简单想法的莫过去先在数组中固定一个数字，再依次

判断数组中剩下的 n-1 个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复

杂度是 O(n

)。

我们假设现在随便在数组中找到两个数。如果它们的和等于输入的数字，那太好了，我们找

到了要找的两个数字；如果小于输入的数字呢？我们希望两个数字的和再大一点。由于数组

已经排好序了，我们是不是可以把较小的数字的往后面移动一个数字？因为排在后面的数字

要大一些，那么两个数字的和也要大一些，就有可能等于输入的数字了；同样，当两个数字

的和大于输入的数字的时候，我们把较大的数字往前移动，因为排在数组前面的数字要小一

些，它们的和就有可能等于输入的数字了。

我们把前面的思路整理一下：最初我们找到数组的第一个数字和最后一个数字。当两个数字

的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数

字往后移动；当相等时，打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。

问题是这样的思路是不是正确的呢？这需要严格的数学证明。感兴趣的读者可以自行证明一

下。

参考代码：

剩余104页未读，继续阅读

搬砖技术工程师

粉丝: 75
资源: 28

二元查找树转排序双向链表的编程面试题解析

.net程序员面试宝典.pdf

Java程序员面试宝典_第二版清晰版

程序员面试宝典 第三版

程序员面试宝典高清第三版

java程序员面试宝典第二版带完美书签

最（全）新面试葵花宝典

软件开发笔试面试题总结精华版

JAVA葵花宝典

mitbbs 面试

程序员面试宝典：经典算法与数据结构实战

最新资源

程序员面试宝典第三版