本文为剑指 offer 系列第六十六篇。
主要知识点为二叉搜索树还有双向链表，这个题目个人感觉比较难，但是题目非常好。
值得我们认真且细致的去理解两者之间的关系，并将这个问题做出来。
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解题思路
- 首先我们要明晰二叉搜索树和双向链表各自的特点。
- 然后在处理的时候可以将这个二叉搜索树分为三部分，左子树，根节点，右子树。我们的目标实际上就是将左子树转化成的双向链表链接上根节点再链接到右子树转化成的双向链表，所以自然就会想到用递归来实现。
- 最后就是细节的处理，要注意在链接左子树和根节点的时候，是将左子树的最大的节点和根节点链接起来，其实就是右下角的节点，
在链接根节点和右子树的时候，是将根节点和右子树中最小的节点进行链接，其实也就是最左下角的节点。
解题代码
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
33
34
35
36
37
38
| /*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree){
if(pRootOfTree==NULL)
return NULL;
if(pRootOfTree->left==NULL&&pRootOfTree->right==NULL)
return pRootOfTree;//如果是叶子结点则直接返回当前节点
TreeNode* left = Convert(pRootOfTree->left);//找到左子树最左端节点
TreeNode* curr = left;
//找到左子树最右侧节点
while(curr!=NULL&&curr->right!=NULL)
curr=curr->right;
//连接根节点和左子树
if(curr!=NULL){
curr->right=pRootOfTree;
pRootOfTree->left = curr;
}
//找到右子树最左端节点
TreeNode* right = Convert(pRootOfTree->right);
//连接根节点和右子树
if(right!=NULL){
pRootOfTree->right = right;
right->left = pRootOfTree;
}
return left!=NULL?left:pRootOfTree;//返回最左边节点的位置
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！