题解 | #二叉搜索树与双向链表#

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    // 封装结构 - 该子树的最大结点和最小结点
    // 这里不涉及到新建TreeNode结点，只用作记录已存在的TreeNode结点
    public class Info {
        // 该子树的最大结点
        TreeNode max;
        // 该子树的最小结点
        TreeNode min;

        public Info(TreeNode max, TreeNode min) {
            this.max = max;
            this.min = min;
        }
    }

    // 主方法
    public TreeNode Convert(TreeNode pRootOfTree) {
        // 根据左程云老师讲的【二叉树递归套路】，先弄明白三件事
        // 1.我要干什么：
        //        令root.left   <->   【左子树】的【最大结点】
        //        令root.right  <->   【右子树】的【最小结点】

        // 2.我需要什么信息：
        //      综上所述，我需要左右子树的【最小结点】和【最大结点】，可以把它们【封装】进一个数据结构中，方便递归函数的return

        // 3.我如何利用两个子树的信息加工出来我的信息：
        //      根据二叉搜索树的性质：
        //      root的【最大结点】 = 【右子树】的【最大结点】 或者 【root】
        //      root的【最小结点】 = 【左子树】的【最小结点】 或者 【root】


        // 调用递归函数生成双向链表，并返回这个双向链表的最左头结点
        Info resultInfo = process(pRootOfTree);

        return resultInfo.min;
    }

    // 递归序遍历二叉树函数 - 返回以root为根结点的子树的最大结点和最小结点
    public Info process(TreeNode root) {
        // 递归出口
        if (root == null) {
            // 当结点为空时，说明这一子树的max和min都是null
            return new Info(null, null);
        }

        // 记录左子树和右子树的最小结点和最大结点
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);

        // 拿到左右子树的Info后做两件事:
        // 1.令root.left <-> 【左子树】的【最大结点】；root.right <-> 【右子树】的【最小结点】
        root.left = leftInfo.max;
        if (leftInfo.max != null) {
            leftInfo.max.right = root;
        }
        root.right = rightInfo.min;
        if (rightInfo.min != null) {
            rightInfo.min.left = root;
        }
        // 2.生成自己的Info信息并返回
        TreeNode myMax = (rightInfo.max != null) ? rightInfo.max : root;
        TreeNode myMin = (leftInfo.min != null) ? leftInfo.min : root;

        return new Info(myMax, myMin);
    }
}