一、题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
二、解题思路
非递归思路：中序遍历二叉搜索树，就是对节点的顺序遍历。依次把节点存储到集合中，然后让集合中的前一个元素指向后一个元素，同时后一个元素指向前一个元素。
//把二叉搜索树转变为排序的双向链表public static TreeNode Convert(TreeNode root) {if(root ==null)return null;//实例化一个ArrayList集合用来存储二叉搜索树中的节点ArrayList<TreeNode>list = new ArrayList<TreeNode>();//才用中序遍历的方式存储节点，就是顺序存储节点midShow(root,list); //让集合中的每个节点元素的右指针指向集合中下一个元素节点 for(int i=0;i<list.size()-1;i++){list.get(i).right = list.get(i+1);} //让集合中的每一个节点元素的左指针指向集合中前一个元素节点 for(int j=1;j<list.size();j++){list.get(j).left = list.get(j-1);}//返回集合中的第一个节点元素return list.get(0);}//中序遍历二叉搜索树，存储到集合中就是顺序存储public static void midShow(TreeNode root,ArrayList<TreeNode>list){if(root !=null) {if(root.left !=null){midShow(root.left,list);}list.add(root);if(root.right !=null){midShow(root.right,list);}} }