剑指offer
26 二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路
1.调整指针
原先指向左子节点的指针调整为链表中指向前一个节点的指针
原先指向右子节点的指针调整为链表中指向后一个节点的指针
2.如何调整
考虑根节点和左右子树的基本情况，因为如果用递归，这种基本情况考虑就可以去将同样的方法用到左右子树上
3.调整步骤
对于这种基本情况，可以分成三个部分来看，根节点10，左子树，右子树，需要做的就是将10与左子树中的最大值连起来，然后把10与右子树中的最小值连起来
现在有个问题就是我们并不知道左子树中的最大值和右子树中的最小值，如果我们知道就好了。但是想到递归，递归到左子树中，如果左子树已转换为双向链表，那么双向链表的最后一个节点就是我们想要的，而右子树中的第一个节点也是我们想要的
上面的代码中有两个参数，一个是根节点，一个是已经转换好的链表的最后一个节点，因为二叉搜索树中序遍历的特性，当遍历到根节点的时候，左子树已经排好序了，所以会有一个左子树已经转换好的链表，而这个链表的最后一个节点即是我们需要和根节点左连的节点
最开始的时候lastNode为null，current为当前子树的根节点
如果左子树存在，那么转换左子树，递归下去，递归返回之后，说明找到了链表的第一个节点，也就是4那个节点，将4的前面节点置为null，此时current为4那个节点，这个时候由于6的4这个左子树已遍历完了，所以需要往上层返回，返回之前需要将current赋值给lastNode，说明4这个左子树的最后一个节点就是4
由于往上返回了一层，此时的current已经是6了，将6的左节点赋值为之前返回的4，判断之前返回的lastNode是否为null，不为空说明需要把根节点和lastNode连起来，其实lastNode为null的情况就只有第一个节点会出现，其他的时候都不会出现。现在已排好序的包括6的左子树以及6本身了，所以此时的lastNode为6
6和4的双向连接就完成了，由于6的右子树存在，又会递归到右边子树去，由于8不存在左右子树，递归下去一层之后current就是8这个节点，但它的左孩子为空，所以不会左边递归下去，将8的左连接与之前的lastNode连接起来，建立双向连接的一条连接，然后由于lastNode不为空，所以又把lastNode的右连接与8连接起来，至此双向连接建立，此时lastNode为8
所以468都已排好序，此时lastNode为8，返回到上一层，也就是根节点10了，在这一层current为10，将current的左连接与lastNode连接起来，如果lastNode存在，将lastNode的右连接与10连接一起，以此建立双向连接。至此就将根节点和左子树都连接起来了，然后就是去转换右子树，现在的lastNode为10，current为14，14有左孩子，所以需要递归到下一层，下一层的current为12，12没有左孩子，所以不用在坐递归，所以12是12这棵子树转换成双向链表的最左边的节点，将lastNode与12连接，也就是10与12连接，此时的lastNode就变成了12，再将12的右子树递归，由于没有右子树，所以直接返回到上一层，上一层的current是14,14与已排好序的lastNode连接，也就是12与14连接，然后lastNode变为14，递归到14的右子树，也就current变为16，16再递归左子树，无左子树，将16与14连接，此时的lastNode变为16，递归右子树，无右子树，所以整个递归工作完成
代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
//双向链表的左边头结点和右边头节点
TreeNode leftHead = null;
TreeNode rightHead = null;
public TreeNode Convert(TreeNode pRootOfTree) {
//递归调用 叶子节点 的左右节点返回null
if(pRootOfTree==null) return null;
//左子树递归遍历
Convert(pRootOfTree.left); //第一次运行时，使最左边叶子节点为链表第一个节点
//初始rightHead==null，将根节点 pRootOfTree 赋值给 左、右头节点
if(rightHead==null){
leftHead = rightHead = pRootOfTree;
}else{
//后续运行，建立双向连接，将右头节点 rightHead 后移到当前根节点 pRootOfTree
rightHead.right = pRootOfTree;
pRootOfTree.left = rightHead;
rightHead = pRootOfTree;
}
//右子树递归遍历
Convert(pRootOfTree.right);
return leftHead;
}
}references
https://blog.csdn.net/u010312474/article/details/100523321
https://blog.csdn.net/weixin_30337251/article/details/95214799
