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

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    // 二叉搜索树中序遍历有序 
    // 我们假设二叉树就三个节点 
    // 为了使空间复杂度为 O(1) 
    // 令 left == pre , right == next;
    public TreeNode Convert(TreeNode root) {
        if(root == null) return null;
        // 左
       TreeNode mleft = Convert(root.left); // 到达最左边 但不确定是最左边的最右边是否有元素 就算是右 那也是 只有右 没有左
       TreeNode cur = mleft;
        while(cur != null && cur.right != null){
            cur.right.left = cur;
            cur = cur.right;
        }
        //根
        if(mleft != null){
            cur.right = root;
            root.left = cur;
        }
       //右 
        TreeNode mright = Convert(root.right); //到达最接近root 的右子节点 找到 mroot 的最左边 
        cur = mright;
        while(cur != null && cur.left != null){
            cur.left.right = cur;
            cur = cur.left;
        }
        if(mright != null){
            root.right = cur;
            cur.left = root;
        }
        return mleft != null ? mleft : root;
    }
}