http://www.lintcode.com/en/problem/convert-binary-search-tree-to-doubly-linked-list/#

method1

divide and conquer, and have to look for the tail because always return head. can be optimized.

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 * Definition for Doubly-ListNode.
 * public class DoublyListNode {
 *     int val;
 *     DoublyListNode next, prev;
 *     DoublyListNode(int val) {
 *         this.val = val;
 *         this.next = this.prev = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param root: The root of tree
     * @return: the head of doubly list node
     */
    public DoublyListNode bstToDoublyList(TreeNode root) {  
        // Write your code here
        if (root == null) {
            return null;
        }   

        DoublyListNode left = bstToDoublyList(root.left);
        DoublyListNode right = bstToDoublyList(root.right);

        DoublyListNode cur = new DoublyListNode(root.val);
        if (root.left == null && root.right == null) {
            return cur;
        }

        if (left != null) {
            DoublyListNode temp = findTail(left);
            temp.next = cur;
            cur.prev = temp;
        }

        if (right != null) {
            right.prev = cur;
            cur.next = right;
        }

        return left != null ? left : cur;

    }

    public DoublyListNode findTail(DoublyListNode root) {
        if (root.next == null) {
            return root;
        }

        return findTail(root.next);
    }
}

method2. divide and conquer with a return type to hold the head and tail.

a little trick for this. left just manage left, right just mange right. otherwise it becomes chaos.

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 * Definition for Doubly-ListNode.
 * public class DoublyListNode {
 *     int val;
 *     DoublyListNode next, prev;
 *     DoublyListNode(int val) {
 *         this.val = val;
 *         this.next = this.prev = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param root: The root of tree
     * @return: the head of doubly list node
     */
    class ReturnType {
        DoublyListNode first;
        DoublyListNode last;
        public ReturnType (DoublyListNode first, DoublyListNode last) {
            this.first = first;
            this.last = last;
        }
    }
    public DoublyListNode bstToDoublyList(TreeNode root) {  
        // Write your code here
        if (root == null) {
            return null;
        }

        ReturnType ans = helper(root);
        return ans.first;

    }

    public ReturnType helper(TreeNode root) {
        if (root == null) {
            return null;
        }

        ReturnType left = helper(root.left);
        ReturnType right = helper(root.right);

        DoublyListNode cur = new DoublyListNode(root.val);
        ReturnType ans = new ReturnType(null, null);

        if (left != null) {
            ans.first = left.first;
            left.last.next = cur;
            cur.prev = left.last.next;
        } else {
            ans.first = cur;
        }

        if (right != null) {
            ans.last = right.last;
            right.first.prev = cur;
            cur.next = right.first;
        } else {
            ans.last = cur;
        }

        return ans;


    }


}