【剑指offer】二叉搜索树与双向链表

题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
1、思路分析
二叉搜索树的中序遍历，同时需要改变结点的指向关系。首先找到二叉搜索树最右边的结点，并将这个过程中经过的结点入栈。接下来就进行弹出操作，保存在cur中，需要尤其注意利用第一个结点对pre和cur进行初始化，其他时候就改变连接关系。最后令pRootOfTree等于当前结点的右子树（中序遍历），再对右子树进行中序遍历操作。
2、代码

import java.util.Stack;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        TreeNode head = null;
        boolean isFirst = true;
        Stack<TreeNode> s = new Stack<>();
        TreeNode pre = null;
        while(!s.isEmpty() || pRootOfTree != null) {
            if(pRootOfTree != null) {
                s.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            }
            else {
                TreeNode cur = s.pop();
                if(isFirst) {
                    isFirst = false;
                    head = cur;
                    pre = cur;
                }
                else {
                    cur.left = pre;
                    pre.right = cur;
                    pre = cur;
                }
                pRootOfTree = cur.right;
            }
        }
        return head;
    }
}