26.二叉搜索树与双向链表 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 思路： 1.明确Convert函数的功能。 输入：输入一个二叉搜索树的根节点。 过程：将其转化为一个有序的双向链表。 输出：返回该链表的头节点。 2.明确成员变量pLast的功能。 pLast用于记录当前链表的末尾节点。 3.明确递归过程。 递归的过程就相当于按照中序遍历，将整个树分解成了无数的小树，然后将他们分别转化成了一小段一小段的双向链表。再利用pLast记录总的链表的末尾，然后将这些小段链表一个接一个地加到末尾。
public class Solution { //中序遍历//递归调用 左 根 右 遍历 TreeNode pLast=null; public TreeNode Convert(TreeNode root) { //递归调用叶子节点的左右节点返回null if(root==null) return null; // 如果左子树为空，那么根节点root为双向链表的头节点 TreeNode head=Convert(root.left); if(head==null){ head=root; } //连接当前节点root和当前链表的尾节点pLast root.left=pLast; if(pLast!=null){//pLast用于记录当前链表的末尾节点。 pLast.right=root; } pLast=root; //将右子树转换为双向链表 Convert(root.right); return head; } }方法一：非递归版 解题思路： 1.核心是中序遍历的非递归算法。 2.修改当前遍历节点与前一遍历节点的指针指向 方法二：递归版 解题思路： 1.将左子树构造成双链表，并返回链表头节点。 2.定位至左子树双链表最后一个节点。 3.如果左子树链表不为空的话，将当前root追加到左子树链表。 4.将右子树构造成双链表，并返回链表头节点。 5.如果右子树链表不为空的话，将该链表追加到root节点之后。 6.根据左子树链表是否为空确定返回的节点。 方法三：改进递归版 解题思路： 思路与方法二中的递归版一致，仅对第2点中的定位作了修改，新增一个全局变量记录左子树的最后一个节点。
