37、二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

链接：https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5

二叉搜索树的根节点大于左子树所有的节点，小于右子树所有的节点。

我们在转换成排序的双向链表时，原先指向左子节点的引用要调整为指向左子树中最大的一个节点，原先指向右子节点的引用要调整为指向右子树中最小的一个节点。

按照中序遍历的顺序，当我们遍历转换到根节点时，它的左子树已经转化成一个排序的链表了，并且链表的最后一个节点是当前值最大的节点。当它和根节点链接起来后，此时链表的最后一个节点就是根节点（当前值最大的节点）。然后接着遍历转换右子树，并把根节点和右子树中最小的节点链接起来。

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

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

}
*/
public class Solution {
    
    // 用于保存链表的最后一个节点
    private TreeNode lastNode = null;
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        convert(pRootOfTree);
        while (lastNode != null && lastNode.left != null) {
            lastNode = lastNode.left;
        }
        return lastNode;
    }
    
    private void convert(TreeNode node) {
        if (node == null) return;
        // 转换左子树为链表
        if (node.left != null) {
            convert(node.left);
        }
        // 将当前节点指向左子树的引用left指向链表的最后一个节点
        node.left = lastNode;
        // 如果链表的最后一个节点不为null（链表不为空），则将链表的最后一个节点的right指向当前节点
        if (lastNode != null) {
            lastNode.right = node;
        }
        // 将lastNode指向链表的最后一个节点
        lastNode = node;
        // 如果当前节点有右子树，则遍历转换右子树
        if (node.right != null) {
            convert(node.right);
        }

    }
}