[数据结构与算法]BiNode

题目描述：

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

示例：

输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]

解题思路：

首先题目要求就是将二叉排序树转换成一个单向链表，但是这个链表的节点还是使用树的节点，只是左孩子都是NULL，右孩子按照大小顺序排列。

我们知道，对于二叉树排序而言，中序遍历的结果是按照从小到大的顺序排列的。所以我们利用中序遍历然后对树中的节点进行修改。

需要使用两个全局变量head 和 pre
head用来定位新的头节点，pre表示待处理的前驱节点

class Solution {
    TreeNode head = null,pre = null;
    public TreeNode convertBiNode(TreeNode root) {
        if(root == null)
            return root;
        convertBiNode(root.left);
        if(head == null){		//定位新的头节点
            head = root;
        }else{
            pre.right = root;	//修改前驱节点的右孩子  让其指向当前节点
        }
        pre = root;			//更改指针pre
        root.left = null;	//左孩子赋空
        convertBiNode(root.right);
        return head;
    }
}