39_二叉搜索树与双向链表

** 要求：**输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：
方法一：使用递归，中序遍历，考虑使用中序遍历访问树的各节点 cur；并在访问每个节点时构建 cur和前驱节点 pre的引用指向；中序遍历完成后，最后构建头节点和尾节点的引用指向即可。（就是遍历到当前节点的时候，对其进行双向连接）。

public class L37_Convert {
    TreeNode0 head,pre;
    public TreeNode0 Convert(TreeNode0 pRootOfTree) {
        if(pRootOfTree==null)return null;
        // 中序遍历
        dfs(pRootOfTree);
        // 进行头尾连接
        pre.right = head;
        head.left = pre;
        return head;
    }
    public void dfs(TreeNode0 cur){
        // 终止条件
        if(cur == null)return;
        // 先遍历左子树节点，直到最左边为空
        dfs(cur.left);
        // 对当前节点进行双向链接
        if(pre!=null)pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        // 遍历右子树节点，直到右边为空
        dfs(cur.right);
    }
}

方法二：非递归，中序遍历，原来同法一，使用栈保存要遍历的结点

   // 方法二，非递归，中序遍历，使用栈
    public TreeNode0 Convert1(TreeNode0 pRootOfTree) {
        if(pRootOfTree==null)return null;
        Stack<TreeNode0> stack = new Stack<>();
        // 定义 pre前一节点， head头节点， cur当前节点
        TreeNode0 pre=null,head=null,cur=null;
        // 将当前节点指向头节点
        cur = pRootOfTree;
        while(!stack.isEmpty()||cur!=null){
            // 首先遍历左子树节点，直到最左边为空，每遍历一个就存栈里
            while(cur!=null){
                stack.add(cur);
                cur = cur.left;
            }
            // 对当前节点进行双向链接
            cur = stack.pop();
            if(pre==null){
                // 此时为双向链表头节点处
                head = cur;
            }else{
                cur.left = pre;
                pre.right = cur;
            }
            pre = cur;
            // 遍历右子树节点
            cur = cur.right;
        }
        // 对头尾节点进行双向链接
        pre.right = head;
        head.left = pre;
        return head;
    }