Problem

Convert a binary search tree to doubly linked list with in-order traversal.

Example
Given a binary search tree:

    4
   / \
  2   5
 / \
1   3
return 1<->2<->3<->4<->5

思路一(Traverse + global variable)

1. 左中右traverse, 建立每个节点, 并连接

    DoublyListNode dummy = new DoublyListNode(0);
    DoublyListNode node = dummy;
    public DoublyListNode bstToDoublyList(TreeNode root) {  
        helper(root);
        return dummy.next;
    }

    private void helper(TreeNode root) {
        if (root == null) return;

        DoublyListNode curt = new DoublyListNode(root.val);
        helper(root.left);
        curt.prev = node;
        node.next = curt;
        node = node.next;
        helper(root.right);
    }

思路二(divide & conquer)

1. 假设root的左右已经转化好了.
2. 左子树需要返回最后一个node, 右子树需要返回第一个node, 所以创建pair class
3. 讨论p1.last 和 p2.first是否为空的情况

    public DoublyListNode bstToDoublyList(TreeNode root) {  
        if (root == null) return null;
        return helper(root).first;
    }

    private Pair helper(TreeNode root) {
        if (root == null) return new Pair();
        if (root.left == null && root.right == null) {
            DoublyListNode node = new DoublyListNode(root.val);
            return new Pair(node, node);
        }

        DoublyListNode curt = new DoublyListNode(root.val);
        Pair p1 = helper(root.left);
        Pair p2 = helper(root.right);

        Pair p = new Pair(curt, curt);
        if (p1.last != null) {
            p1.last.next = curt;
            curt.prev = p1.last;
            p.first = p1.first;
        }
        if (p2.first != null) {
            p2.first.prev = curt;
            curt.next = p2.first;
            p.last = p2.last;
        }

        return p;
    }

    class Pair {
        DoublyListNode first;
        DoublyListNode last;

        public Pair () {};

        public Pair (DoublyListNode f, DoublyListNode l) {
            first = f;
            last = l;
        }
    }