题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
二叉搜索树的定义：
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
所要求的为排序列表，根据二叉搜索树的定义我们可以知道，二叉搜索树的中序遍历便是有序的。所以我们可以中序遍历二叉树。
image
解法一：
通过递归不断地将节点与其排序好的左右子树连接
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return null;
}
TreeNode res = ConvertCore(pRootOfTree);
while(res.left != null) {
res = res.left;
}
return res;
}
public TreeNode ConvertCore(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return null;
}
//获得排序好的左子树
TreeNode left = ConvertCore(pRootOfTree.left);
if(left != null) {
//获得左子树的最右节点
while(left.right != null) {
left = left.right;
}
//将排序好的左子树与根节点连接
left.right = pRootOfTree;
pRootOfTree.left = left;
}
//获得排序好的右子树
TreeNode right = ConvertCore(pRootOfTree.right);
if(right != null) {
//获得右子树的最左节点
while (right.left != null) {
right = right.left;
}
//将排序好的右子树与根节点连接
pRootOfTree.right = right;
right.left = pRootOfTree;
}
return pRootOfTree;
}
}
解法二：
解法一中要不断地靠循环来确定左右子树的最右和最左节点，时间效率较低。我们知道，中序遍历过程是有序的，我们可以使用一个指针保存当前中序遍历的点，依次将中序遍历经过的点连接起来便可以得到有序的双向链表，省去了大量的循环操作。
public class Solution {
TreeNode current = null;
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return null;
}
ConvertCore(pRootOfTree);
while(current.left != null) {
current = current.left;
}
return current;
}
public void ConvertCore(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return ;
}
ConvertCore(pRootOfTree.left);
//记录二叉搜索树中最左边的节点即最小节点
if(current == null) {
current = pRootOfTree;
}
//连入新节点并更新双向链表的最右节点
else{
current.right = pRootOfTree;
pRootOfTree.left = current;
current = pRootOfTree;
}
ConvertCore(pRootOfTree.right);
}
}
在上面的代码中，使用current来记录已经转换好的链表的最后一个节点。 例如当前节点为10的时候，current为8，将10与8连接后，current更新为10。接着遍历右子树，右子树的第一个点为12，将10和12连接起来，current更新为12。以此类推。
解法三：
解法二中用一个current保存中序遍历经过的节点，在最后返回时仍需要通过循环从current获得初始节点，我们如果再用一个指针来保存初始节点，便可以免去 这个循环操作，在数据量较大时节省一部分时间。
public class Solution {
//双向链表的头节点
TreeNode left = null;
//中序遍历中依次经过的点，相当于解法二的current
TreeNode right = null;
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return null;
}
Convert(pRootOfTree.left);
//保存双向链表的头节点
if(right == null) {
left = pRootOfTree;
right = pRootOfTree;
}
//中序遍历过程中进行连接，并更新已获得的双向链表的尾节点
else {
right.right = pRootOfTree;
pRootOfTree.left = right;
right = pRootOfTree;
}
Convert(pRootOfTree.right);
return left;
}
}
