//题目：输入一个二叉树，将其用中序遍历的顺序变为一个双向链表
//解法：递归的中序遍历树
public class Main {
static TreeNode head = null;
static TreeNode realHead = null;
public static void main(String[] args){
TreeNode t = new TreeNode();
t.data = 2;
t.left = new TreeNode();
t.left.data = 1;
t.left.left = new TreeNode();
t.left.right = new TreeNode();
t.left.left.data = 4;
t.left.right.data = 5;
t.right = new TreeNode();
t.right.data = 3;
Convert(t);
System.out.println();
}
public static TreeNode Convert(TreeNode pRootOfTree) {
ConvertSub(pRootOfTree);
return realHead;
}
private static void ConvertSub(TreeNode pRootOfTree) {
if(pRootOfTree==null) return;
ConvertSub(pRootOfTree.left); //先遍历左子树，然后进行操作，最后遍历右子树
if (head == null) {
head = pRootOfTree;
realHead = pRootOfTree;
} else {
head.right = pRootOfTree;
pRootOfTree.left = head;
head = pRootOfTree;
}
ConvertSub(pRootOfTree.right);
}
}
