题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

示例

输入： {10,6,14,4,8,12,16}
输出： From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
**说明：**输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。

思路方法

观察题目的特点我们可以了解到，输出是按照中序遍历输出的，那么这就成为了我们题目的突破点。
要让输出的链表是双向链表，那么就需要通过二叉树的左右子树的指向发生改变来实现。
两个重要的全局变量：
1、head：记录输出的头节点
2、pre：记录遍历当前的上一个节点，在下方代码的第一次判空中：因为当遍历到最左下的节点时，其就是为输出链表的头节点，pre也就不会再为空，那么head就固定了，也就是二叉树的左下节点，所以这两个变量都需定义为全局变量。

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode head = null;
    public TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        Convert(pRootOfTree.left);
        if(pre==null){
            pre = pRootOfTree;
            head = pRootOfTree;
        }else{
            pre.right = pRootOfTree;
            pRootOfTree.left  = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }     
}