Convert Binary Search Tree to So

https://www.cnblogs.com/grandyang/p/9615871.html
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/
给定一个二叉搜索树，把这个BST变成一个双向链表，这个二叉搜索数的left和right节点就当前后指针

思路

• 总体思想是中序遍历&& 递归
• 变量head记录结果双向链表的头结点
• 变量pre 记录结果双向链表的尾节点
  理解上面三点，下面代码就能看懂了

 //https://www.cnblogs.com/grandyang/p/9615871.html
    //https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/

    TreeNode pre, head;

    public TreeNode treeToDoublyList(TreeNode root) {
        if (root == null) {
            return null;
        }
        dfs(root);
        //这两句话把这个链表变成了一个环，可能题目这么要求？
        head.left = pre;
        pre.right = head;
        return head;
    }

    //TreeNode没法引用传递，需要一个全局变量
    public void dfs(TreeNode cur) {
        if (cur == null) {
            return;
        }
        //中序遍历，先找到最左的叶子节点
        dfs(cur.left);

        //pre表示迭代后双向链表的尾节点
        if (pre != null) {
            pre.right = cur;
        } else {
            //head表示变成双向链表的头节点
            //当pre为空，表明这是整棵树的最左边那个叶子节点，
            head = cur;
        }
        cur.left = pre;
        pre = cur;

        dfs(cur.right);
    }