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

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

递归：

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;        }    }}

注意：本次编程中，发现了一个问题，在递归中，每次传入的形参是不同的，如果递归了10次，在第10次中，如果给形参赋值，但在第8次，形参值仍然为空。

非递归，需要用到栈

public static TreeNode convertWithStack(TreeNode root){        if(root == null)            return null;        TreeNode cur = root;        TreeNode pre = null;        Stack
     
       stack = new Stack
      
       ();        while(!stack.isEmpty() || cur != null){            while(cur != null){                stack.push(cur);                cur = cur.left;            }            cur = stack.pop();            if(pre == null){                root = cur;                pre = cur;            }else{                pre.right = cur;                cur.left = pre;                pre = cur;            }            cur = cur.right;        }        return root;    }