剑指Offer - 九度1503 - 二叉搜索树与双向链表
2024-09-18 02:59:21
剑指Offer - 九度1503 - 二叉搜索树与双向链表
2014-02-05 23:39
- 题目描述：
-
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
- 输入：
-
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个数n(0<n<1000)，代表测试样例的个数。
接下来的n行，每行为一个二叉搜索树的先序遍历序列，其中左右子树若为空则用0代替。
- 输出：
-
对应每个测试案例，
输出将二叉搜索树转换成排序的双向链表后，从链表头至链表尾的遍历结果。
- 样例输入：
-
1
2 1 0 0 3 0 0
- 样例输出：
-
1 2 3
题意分析：
这道题要求将二叉搜索树转换成双向链表，我的思路是进行后序遍历。先将左右子树搞定以后，再处理根节点。
那么，怎么处理呢？在转换完成之后，根节点的左边是左子树最大的节点(左子树最偏右的)，右边是右子树最小的节点(右子树最偏左的)。
因此，在递归过程中，需要获得这两个参数，具体做法请参见代码。其中最关键的四个参数：
1. pll：左子树最靠左的节点
2. plr：左子树最靠右的节点
3. prl：右子树最靠左的节点
4. prr：右子树最靠右的节点
虽然也可以通过O(h)的复杂度(h为树的高度)查找出上述四个节点，但那么做的话，就重复遍历了很多节点，整体复杂度也变成了O(n * log(n))。
所以我们在递归的过程中随时更新这些参数即可。
时间复杂度为O(n)，空间复杂度O(n)，n表示树的节点个数。
// 690545 zhuli19901106 1503 Accepted 点击此处查看所有case的执行结果 1024KB 2642B 70MS
// 201402041916
//#define MY_DEBUG
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std; typedef struct st{
public:
int key;
struct st *ll;
struct st *rr;
st(int _key): key(_key) {}
}st; void convertBSTtoDoubleLinkedList(st *root, st *&left_most, st *&right_most)
{
if (root == NULL) {
return;
} if (root->ll == NULL && root->rr == NULL) {
left_most = root;
right_most = root;
} st *pll = NULL, *plr = NULL, *prl = NULL, *prr = NULL;
if (root->ll != NULL) {
convertBSTtoDoubleLinkedList(root->ll, pll, plr);
} else {
pll = plr = root;
}
if (root->rr != NULL) {
convertBSTtoDoubleLinkedList(root->rr, prl, prr);
} else {
prl = prr = root;
}
left_most = pll;
right_most = prr;
if (plr != root) {
plr->rr = root;
root->ll = plr;
}
if (prl != root) {
prl->ll = root;
root->rr = prl;
}
} void constructBST(st *&root)
{
int tmp; scanf("%d", &tmp);
if (tmp == ) {
root = NULL;
} else {
root = new st(tmp);
constructBST(root->ll);
constructBST(root->rr);
}
} #ifdef MY_DEBUG
void postorderTraversal(const st *root)
{
if (root == NULL) {
return;
}
postorderTraversal(root->ll);
postorderTraversal(root->rr);
printf("%d ", root->key);
}
#endif st *deleteList(st *head)
{
if (NULL == head) {
return head;
}
st *ptr1, *ptr2; ptr1 = head;
while (ptr1 != NULL) {
ptr2 = ptr1;
ptr1 = ptr1->rr;
delete ptr2;
} return NULL;
} st *deleteTree(st *root)
{
if (NULL == root) {
return NULL;
}
if (root->ll != NULL) {
root->ll = deleteTree(root->ll);
}
if (root->rr != NULL) {
root->rr = deleteTree(root->rr);
}
delete root;
return NULL;
} int main()
{
int cc, ci;
st *root = NULL;
st *left_most, *right_most, *ptr; while (scanf("%d", &cc) == ) {
for (ci = ; ci < cc; ++ci) {
root = NULL;
constructBST(root); // used to verify the tree
#ifdef MY_DEBUG
postorderTraversal(root);
printf("\n");
#endif left_most = right_most = NULL;
convertBSTtoDoubleLinkedList(root, left_most, right_most);
ptr = left_most;
while (ptr != NULL) {
printf("%d ", ptr->key);
ptr = ptr->rr;
}
printf("\n");
deleteList(left_most);
root = left_most = right_most = NULL;
}
} return ;
}
最新文章
- CCNA网络基础（一）
- WebForm复杂控件
- React Native的组件ListView
- Git克隆
- SQL Server FileStream
- 学习Learn Python The Hard Way 前言中的一段话，可与君共勉
- WCF之各种WCF引用方式
- VC depends使用说明
- gem安装时出现 undefined method `size' for nil:NilClass (NoMethodError) 的解决办法
- BZOJ 2626 JZPFAR（KD-tree）
- glusterfs快速安装
- Creating your own header file in C
- asp.net core webapi文件上传
- 42.Odoo产品分析 (四) – 工具板块(10) – 问卷(2)
- get、put、post、delete含义与区别
- StarUML[3.1.0]官方安装破解版[app.asar]
- php核心技术与最佳实践（笔记一）
- 一篇文章说清楚mysql索引
- Kali学习笔记27：Burpsuite（上）
- koa服务器搭建基础