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

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 {
    private TreeNode prev = null;//记录当前节点的前序节点
    private TreeNode head = null;//记录链表头节点

    public TreeNode Convert(TreeNode pRootOfTree) {
        //将BST转换为排序双向链表：每个节点的left指针指向前驱节点，right指向后继节点
        //1. 解决思想：中序遍历：左--> 根--> 右 + 指针修改
        //2. 指针操作步骤：
        //创建指针prev：记录当前节点的前驱节点。
        //创建指针cur指向当前节点。当遍历到cur时，将cur.left指向prev，将prev.right指向cur
        //更新prev为当前节点cur
        
        if(pRootOfTree == null){
            return null;
        }

        inorder(pRootOfTree);
        

        return head;
    }

    //inorder方法实现中序遍历
    private void inorder(TreeNode cur){
        if(cur == null){
            return;
        }
        //1. 遍历左子树
        inorder(cur.left);
        //2. 处理根节点
        if(prev == null){
            //第一个节点为链表表头
            head = cur;
        }else{
            prev.right = cur;
            cur.left = prev;
        }
        prev = cur;
        //3. 遍历右子树
        inorder(cur.right);
    }

}