输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
链接：https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
二叉搜索树的根节点大于左子树所有的节点，小于右子树所有的节点。
我们在转换成排序的双向链表时，原先指向左子节点的引用要调整为指向左子树中最大的一个节点，原先指向右子节点的引用要调整为指向右子树中最小的一个节点。
按照中序遍历的顺序，当我们遍历转换到根节点时，它的左子树已经转化成一个排序的链表了，并且链表的最后一个节点是当前值最大的节点。当它和根节点链接起来后，此时链表的最后一个节点就是根节点（当前值最大的节点）。然后接着遍历转换右子树，并把根节点和右子树中最小的节点链接起来。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
// 用于保存链表的最后一个节点
private TreeNode lastNode = null;
public TreeNode Convert(TreeNode pRootOfTree) {
convert(pRootOfTree);
while (lastNode != null && lastNode.left != null) {
lastNode = lastNode.left;
}
return lastNode;
}
private void convert(TreeNode node) {
if (node == null) return;
// 转换左子树为链表
if (node.left != null) {
convert(node.left);
}
// 将当前节点指向左子树的引用left指向链表的最后一个节点
node.left = lastNode;
// 如果链表的最后一个节点不为null（链表不为空），则将链表的最后一个节点的right指向当前节点
if (lastNode != null) {
lastNode.right = node;
}
// 将lastNode指向链表的最后一个节点
lastNode = node;
// 如果当前节点有右子树，则遍历转换右子树
if (node.right != null) {
convert(node.right);
}
}
}
