剑指Offer面试题27：二叉搜索树与双向链表

题目描述：输入一课二叉搜索树，将该二叉树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。比如，输入图中的二叉搜索树，则输出转换之后的双向链表

从中我们可以发现双向链表中的结点顺序和二叉搜索树的中序遍历得到的序列顺序是一样的。
我们可以使用递归和非递归两种方式实现这道题的求解

非递归方式：我们借助栈结构，同时我们需要记录当前结点和前一个结点，这样我们就能将当前结点的左指针和前一个结点的右指针指向前一个结点和当前结点。

if(root == null)
    return null;
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
TreeNode prev = null;    //用于保存遍历的前一个结点
boolean isFirst = true;
while(curr != null || !stack.isEmpty()){
    while(curr != null){
        stack.push(curr);
        curr = curr.left;
    }
    curr = stack.pop();
    if(isFirst){                  //*
        root = curr;          //中序遍历的第一个结点记为双向链表的第一个结点
        prev = curr;
        isFirst = false;
    }else{
        curr.left = prev;
        prev.right = curr;
        prev = curr;
    }                             //*
    curr = curr.right;
}
return root;

其实上述代码中，和之间的代码去掉后就成了二叉树的中序遍历非递归实现！

递归实现：
1.一直向左孩子递归，直到最左边的叶结点
2.然后将最左边的结点和lastNode结点的指针指向正确的位置
3.将目前的值赋给lastNode值
4.同样的方式右孩子递归，连接右子树

private TreeNode lastNode = null;
public TreeNode Convert(TreeNode pRootOfTree) {
    if(pRootOfTree == null)
        return null;
    while(lastNode != null && lastNode.left != null)
        lastNode = lastNode.left;
    return lastNode;
}
private void ConvertNode(TreeNode root){
    if(root == null)
        return;
    TreeNode curr = root;
    if(curr.left != null){
        ConvertNode(curr.left);  //一直递归直到遍历到最左边的叶结点,从最左边的结点开始连接
    }
    curr.left = lastNode;
    if(lastNode != null){
        lastNode.right = curr;
    }
    lastNode = curr;
    if(curr.right != null){
        ConvertNode(curr.right);
    }
}