@TOC

426. 将二叉搜索树转化为排序的双向链表

将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。

对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/convert-binary-search-tree-to-sorted-doubly-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、二叉树递归套路

X为头的整棵二叉树请变成有序双向链表返回info信息
info信息两个:转完之后的链表的头指针，和转完之后链表的尾指针而且只返回两个变量，
但是我认为中间全部串好了。

我们调用f(4)的时候,有f(2)和f(6),将f(2)和f(6)的首尾相连
调用f(2)的时候有f(1)和f(3),将f(1)和f(3)首尾相连
调用f(6)的时候有f(5)和f(7),将f(5)和f(7)首尾相连

代码

public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node treeToDoublyList(Node head) {
        if (head == null) {
            return null;
        }
        Info allInfo = process(head);
        allInfo.end.right = allInfo.start;
        allInfo.start.left = allInfo.end;
        return allInfo.start;
    }

    public static class Info {
        public Node start;
        public Node end;

        public Info(Node start, Node end) {
            this.start = start;
            this.end = end;
        }
    }

    public static Info process(Node X) {
        if (X == null) {
            return new Info(null, null);
        }
        Info lInfo = process(X.left);
        Info rInfo = process(X.right);
        if (lInfo.end != null) {
            lInfo.end.right = X;
        }
        X.left = lInfo.end;
        X.right = rInfo.start;
        if (rInfo.start != null) {
            rInfo.start.left = X;
        }
        // 整体链表的头    lInfo.start != null ? lInfo.start : X
        // 整体链表的尾    rInfo.end != null ? rInfo.end : X
        return new Info(lInfo.start != null ? lInfo.start : X, rInfo.end != null ? rInfo.end : X);
    }