두 갈래 찾기 트 리 가 질서 있 는 양 방향 링크 로 바 뀌 었 습 니 다.

/** 
     * 
     *     ： 
     *    http://stackoverflow.com/questions/11511898/converting-a-binary-search-tree-to-doubly-linked-list#answer-11530016 
     *            ，       ，root         ，      
     *  root          
     */  
    public static TreeNode convertBST2DLLRec(TreeNode root) {  
        root = convertBST2DLLSubRec(root);  
          
        // root         ，      root       
        while(root.left != null){  
            root = root.left;  
        }  
        return root;  
    }  
      
    /** 
     *      BST     (DLL) 
     */  
    public static TreeNode convertBST2DLLSubRec(TreeNode root){  
        if(root==null || (root.left==null && root.right==null)){  
            return root;  
        }  
          
        TreeNode tmp = null;  
        if(root.left != null){          //        
            tmp = convertBST2DLLSubRec(root.left);  
            while(tmp.right != null){   //         
                tmp = tmp.right;  
            }  
            tmp.right = root;       //           root    
            root.left = tmp;  
        }  
        if(root.right != null){     //        
            tmp = convertBST2DLLSubRec(root.right);  
            while(tmp.left != null){    //         
                tmp = tmp.left;  
            }  
            tmp.left = root;        //           root    
            root.right = tmp;  
        }  
        return root;  
    } 

    /** 
     *                      
//   *   inorder traversal    
     */  
    public static TreeNode convertBST2DLL(TreeNode root) {  
        if(root == null){  
            return null;  
        }  
        Stack stack = new Stack();  
        TreeNode cur = root;        //           
        TreeNode old = null;            //             
        TreeNode head = null;       //      
          
        while( true ){  
            while(cur != null){     //                    
                stack.push(cur);  
                cur = cur.left;  
            }  
              
            if(stack.isEmpty()){  
                break;  
            }  
                  
            //             ，          
            cur = stack.pop();  
            if(old != null){  
                old.right = cur;  
            }  
            if(head == null){       // /               
                head = cur;  
            }  
              
            old = cur;          //   old  
            cur = cur.right;    //          
        }  
          
        return head;  
    }