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

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 head = pRootOfTree;
        while (head.left != null) {
            head = head.left;
        }
        innerConvert(pRootOfTree);
        return head;
    }

    private void innerConvert(TreeNode root) {
        if (root == null) return;
        TreeNode left = root.left;
        TreeNode right = root.right;
        innerConvert(left);
        innerConvert(right);


        if (right != null) {
            TreeNode after = right;
            while (after.left != null) {
                after = after.left;
            }
            after.left = root;
            root.right = after;
        }

        if (left != null) {
            TreeNode pre = left;
            while (pre.right != null) {
                pre = pre.right;
            }
            pre.right = root;
            root.left = pre;
        }
    }
}