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

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 null;
        TreeNode[] res = convert(pRootOfTree);
        return res[0];
    }

    public TreeNode[] convert(TreeNode root) {
        //TreeNode[0]是转换链表的最左侧节点
        //TreeNode[1]是转换链表的最右侧节点
        if (root.left == null && root.right == null) return new TreeNode[] {root, root};

        TreeNode[] leftRes = new TreeNode[2];
        TreeNode[] rightRes = new TreeNode[2];
        TreeNode[] curRes = new TreeNode[2];

        if (root.left != null) {
            leftRes = convert(root.left);
            //拼接
            leftRes[1].right = root;
            root.left = leftRes[1];
            curRes[0] = leftRes[0];
        } else {
            curRes[0] = root;
        }

        if (root.right != null) {
            rightRes = convert(root.right);
            //拼接
            rightRes[0].left = root;
            root.right = rightRes[0];
            curRes[1] = rightRes[1];
        } else {
            curRes[1] = root;
        }

        return curRes;
    }
}