# 0426. Convert Binary Search Tree to Sorted Doubly Linked List
###### tags: `Leetcode` `FaceBook` `Medium` `Tree` `Double Linked List`
Link: https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
## 思路
递归
一直保存现在遍历到的最大值和最小值
最大值和current node连在一起
最后最小值和最大值连在一起
## Code

class Solution {
    Node first = null;
    Node last = null;
    public Node treeToDoublyList(Node root) {
        if(root == null) return root;
        createDoubleList(root);
        first.left = last;
        last.right = first;
        return first;
    }
    
    public void createDoubleList(Node root){
        if(root == null) return;
        createDoubleList(root.left);
        if(last != null){
            last.right = root;
            root.left = last;
        }
        else{
            first = root;
        }
        last = root;
        createDoubleList(root.right);
    }
}

## Result
Runtime: 0 ms, faster than **100.00%** of Java online submissions for Convert Binary Search Tree to Sorted Doubly Linked List.
Memory Usage: 38.4 MB, less than **53.56%** of Java online submissions for Convert Binary Search Tree to Sorted Doubly Linked List.