将二叉查找树转换成双向链表

Lintcode上的一道题，昨天下班之前顺手做了一下：将一个二叉查找树按照中序遍历转换成双向链表。

思路：递归中序遍历，用栈存储链表节点构造节点的前后关系。

public class Solution { 
    List<DoublyListNode> treeNodes = new ArrayList<>();

    /**
     * @param root: The root of tree
     * @return: the head of doubly list node
     */
    public DoublyListNode bstToDoublyList(TreeNode root) {
        if (root == null) {
            return null;
        }
        inorderTraversal(root);
        return treeNodes.get(0);
    }

    public void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        DoublyListNode node = new DoublyListNode(root.val);
        int top = treeNodes.size() - 1;
        if (top >= 0) {
            DoublyListNode topNode = treeNodes.get(top);
            node.prev = topNode;
            topNode.next = node;
        }
        treeNodes.add(node);
        inorderTraversal(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        BstToDoublyList list = new BstToDoublyList();
        DoublyListNode node = list.bstToDoublyList(root);
        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }
}