算法1

(递归) $O(n)$

从题目可以看出，要将二叉搜索树输出为排序的双向链表。

首先排序，可以很容易的看出，当我们对二叉搜索树进行中序遍历时，恰好是排好序的，所以递归进行中序遍历。

在左子树和右子树的递归之间，进行两个节点之间的操作即可。

代码如下

java 代码

class Solution {
    public TreeNode convert(TreeNode root) {
        if(root==null)
        return null;

        if(root.left==null&&root.right==null)
        return root;

        TreeNode left = convert(root.left);
        TreeNode node = left;

        while(node!=null&&node.right!=null){
            node = node.right;
        }

        if(left!=null){
            node.right = root;
            root.left = node;
        }

       TreeNode right=convert(root.right);

        if(right!=null)
         {
            root.right=right;
            right.left=root;
        }

        return left!=null?left:root;
    }

}