牛客网剑指Offer-树篇-JZ36 二叉搜索树与双向链表

题目

来源：JZ36 二叉搜索树与双向链表
描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

数据范围：输入二叉树的节点数 0≤n≤1000，二叉树中每个节点的值 0≤val≤1000
要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n)

注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出
输入描述：
二叉树的根节点
返回值描述：
双向链表的其中一个头节点。
示例1
输入：
{10,6,14,4,8,12,16}
返回值：
From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明：
输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
示例2
输入：
{5,4,#,3,#,2,#,1}
返回值：
From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
说明：
5
/
4
/
3
/
2
/
1
树的形状如上图

解析

基础：空间O(n)
原地操作还是有一定难度的，所以空间O(n)的解法还是很有价值的。正如我在二叉搜索树的第k个节点中所说的，中序遍历BST即可得到升序数组。所以只需中序遍历BST，同时创建节点即可，但这里有个坑：链表是动态创建的，所以一般需要额外创建一个头节点来使操作更方便，或保存当前节点的上一节点也行，这里用前者。

TreeNode* head, *q;
void InOrderTrav(TreeNode* p) {if (!p) return;InOrderTrav(p->left);TreeNode* tmp = new TreeNode(p->val);q->right = tmp;tmp->left = q;q = q->right;InOrderTrav(p->right);
}
TreeNode* Convert(TreeNode* root) {if (!root) return NULL;head = new TreeNode(0);q = head;InOrderTrav(root);head->right->left = NULL;return head->right;
}

进阶：空间O(1)
如果不能创建新节点，则需要额外的指针，这个指针的作用很容易想到，就是保存上一节点，所以总共需要两个额外指针：head,pre。现在有个难点：head如何指向第一个节点？由于递归的性质，当递归到树的最左下节点时，当前节点即第一个节点，所以我们需要在递归左右子树之间对head的值行判断：假设head初始值是空，那么当head为空时，使head指向当前节点，pre再指向head，否则链接当前节点和pre。注意题目要求返回head，所以在递归完左右子树后，要返回head。

TreeNode* head = NULL, *pre;
TreeNode* Convert(TreeNode* p) {if (!p) return NULL;Convert(p->left);if (!head) {head = p;pre = head;} else {pre->right = p;p->left = pre;pre = p;}Convert(p->right);return head;
}