package java_jianzhioffer_algorithm;
/**
* 题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
* 要求不能创建任何新的结点，只能调整树中结点指针的指向。
* @author hexiaoli
* 思考：
* 二叉搜索树的中序遍历的序列，就是排序的顺序。
根据排序双向链表的定义，根结点将和它的左子树的最大一个结点链接起来，同时它还将和它右子树最小的结点链接起来。
在中序遍历过程中，当遍历到根结点时，它的左子树已经转换成一个排序的好的双向链表
并且当前指针指向链表中最后一个的结点。将其与根结点链接起来，此时根结点就成了最后一个结点，
接着遍历右子树，并把根结点和右子树中最小的结点链接起来。
*/
class TreeNodec{
int val = 0;
TreeNodec left = null;
TreeNodec right = null;
public TreeNodec(int val) {
this.val = val;
}
}
public class Convert {
//双向链表的左边头结点和右边头节点
static TreeNodec leftHead = null;
static TreeNodec rightHead = null;
public static TreeNodec convert(TreeNodec pRootOfTree) {
//递归调用叶子节点的左右节点返回null
if(pRootOfTree==null) return null;
//第一次运行时，它会使最左边叶子节点为链表第一个节点
convert(pRootOfTree.left);
if(rightHead==null){
leftHead= rightHead = pRootOfTree;
}else{
//把根节点插入到双向链表右边，rightHead向后移动
rightHead.right = pRootOfTree;
pRootOfTree.left = rightHead;
rightHead = pRootOfTree;
}
//把右叶子节点也插入到双向链表（rightHead已确定，直接插入）
convert(pRootOfTree.right);
//返回左边头结点
return leftHead;
}
public static void main(String[] args) {
TreeNodec pRootOfTree = new TreeNodec(4);
TreeNodec left1 = new TreeNodec(2);
TreeNodec right1 = new TreeNodec(6);
TreeNodec left2 = new TreeNodec(1);
TreeNodec right2 = new TreeNodec(3);
TreeNodec left3 = new TreeNodec(5);
TreeNodec right3 = new TreeNodec(7);
pRootOfTree.left=left1;
pRootOfTree.right=right1;
left1.left=left2;
left1.right=right2;
right1.left=left3;
right1.right=right3;
TreeNodec result ;
result = convert(pRootOfTree);
System.out.println(result.val);
}
}
