将二叉搜索树转换为有序的双向链表

题目：给出一个二叉搜索树，要求将它转换为有序的双向链表，要求不能添加新的节点空间。

思路：有序的双向链表，二叉搜索树的中序遍历是有序的。

递归：

public class TreeNodeDemo {private static TreeNode head = null;private static TreeNode tail = null;public static void main(String[] args) {TreeNode tn10 = new TreeNode(10);TreeNode tn15 = new TreeNode(15);TreeNode tn5 = new TreeNode(5);TreeNode tn12 = new TreeNode(12);TreeNode tn20 = new TreeNode(20);TreeNode tn18 = new TreeNode(18);TreeNode tn25 = new TreeNode(25);tn15.left = tn10;tn15.right = tn20;tn10.left = tn5;tn10.right = tn12;tn20.left = tn18;tn20.right = tn25;TreeNode node = transTreeToList(tn15);while(node.right != null){System.out.print(node.val+" ");node = node.right;}}/*** root是二叉树的根，转换为双向链表要返回链表的头节点，不然找不到* @param root*/public static TreeNode transTreeToList(TreeNode root){if(root == null)return null;transTreeToList(root.left);if(head == null){head = root;tail = root;}else{root.left = tail;tail.right = root;tail = root;}transTreeToList(root.right);return head;}private static class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}}
}