题解 | #二叉搜索树与双向链表# 中序遍历并连接节点

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 {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return pRootOfTree;
        }
        return merge(pRootOfTree)[0];
    }

    private TreeNode[] merge(TreeNode root) {
        // 递归终点
        if (root == null) {
            return new TreeNode[]{null, null};
        }

        // 左边链表化结果
        TreeNode[] leftPart = merge(root.left);
        
        // 右边链表化结果
        TreeNode[] rightPart = merge(root.right);

        // 连接左右两边
        if (leftPart[1] != null) {
            leftPart[1].right = root;
        }
        root.left = leftPart[1];
        root.right = rightPart[0];
        if (rightPart[0] != null) {
            rightPart[0].left = root;
        }
        
        // 返回连接后的结果[head, tail]
        TreeNode head = null;
        if (leftPart[0] != null) {
            head = leftPart[0];
        } else {
            head = root;
        }
        TreeNode tail = null;
        if (rightPart[1] != null) {
            tail = rightPart[1];
        } else {
            tail = root;
        }
        return new TreeNode[]{head, tail};
    }
}