BstToDoublyLinkedList.java

/**
 * 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) {
        DoublyListNode[] result = helper(root);
        return result[0];
    }
    
    private DoublyListNode[] helper(TreeNode node) {
        DoublyListNode[] result = new DoublyListNode[2];
        if (node == null) return result;
        DoublyListNode[] left = helper(node.left);
        DoublyListNode[] right = helper(node.right);
        DoublyListNode curr = new DoublyListNode(node.val);
        
        if (left[1] == null) {
            result[0] = curr;
        } else {
            curr.prev = left[1]; 
            left[1].next = curr; 
            result[0] = left[0]; 
        }
        
        if (right[0] == null) {
            result[1] = curr; 
        } else {
            curr.next = right[0]; 
            right[0].prev = curr; 
            result[1] = right[1]; 
        }
        
        return result; 
    }
}