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

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

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

    }

}
*/
public class Solution {
    TreeNode pre = null;
    TreeNode root = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        //左根右遍历一遍 节点即按照从大到小排列的
        //4 6 8 10 记录上一个的节点
        if(pRootOfTree==null) return null;
        //左
        Convert(pRootOfTree.left); 
        //root记录最小值的结点 eg4 作为链表开头返回
        //由于左根右的遍历顺序 因此第一次走到此处根的时候
        //必为一直往左走的最小值结点 因此赋值给root
        if(root==null){
            root = pRootOfTree;
        }
        //上一个节点eg4 值比当前结点小eg6
        if(pre!=null){
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
        }
        //要从自己这个结点往右子树走 自己变成了pre结点
        pre = pRootOfTree;
        Convert(pRootOfTree.right);
        return root;
    }
    
}

由于是有序的 考虑中序遍历

每次记录下pre结点，然后修改其指针