1、前言

2、思路

二叉搜索树的中序遍历，最后的 dfs 返回时，还需要处理一下，让头跟尾连起来。

3、代码

class Solution {

    private Node pre = null;

    public Node treeToDoublyList(Node root) {
        if(root == null){
            return root;
        }

        Node head = new Node();
        pre = head;
        dfs(root);
        Node res = head.right;
        pre.right = res;
        res.left = pre;

        return res;
    }

    private void dfs(Node root){
        if(root == null){
            return;
        }

        dfs(root.left);

        pre.right = root;
        root.left = pre;
        pre = root;

        dfs(root.right);
    }
}