二叉搜索树与双向链表

不需要额外空间，中序遍历，修改指针即可。

public class Solution 
{
    public TreeNode Convert(TreeNode pRootOfTree) 
    {
        if(pRootOfTree==null || (pRootOfTree.left==null && pRootOfTree.right==null)) 
            return pRootOfTree;
        return convert(pRootOfTree, false);
    }

    private static TreeNode convert(TreeNode node, boolean is_left)
    {
        if(node==null) return null;
        node.left = convert(node.left, true);    //使用左子树递归，返回的是左子树最右边的结点
        if(node.left!=null)
            node.left.right = node;
        node.right = convert(node.right, false);    //使用右子树递归，返回的是右子树最左边的结点
        if(node.right!=null)
            node.right.left = node;
        // 如果是左子树，则返回最右侧结点
        while(is_left && (node.right!=null))
            node = node.right;
        //如果是右子树，则返回最左侧结点
        while((!is_left)&& (node.left!=null))
            node = node.left;
        return node;
    }

}