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

二叉搜索树：左节点的值必定小于右节点的值

中序遍历：先中序遍历左节点，在遍历根节点，最后中序遍历右节点

题目要求将二叉搜索树转换成升序的双向链表（左节点为前驱，右节点为后继），可以联想到可以使用二叉树的中序遍历来保证节点的升序效果。在中序遍历过程中修改节点指针指向来实现升序双向链表。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Convert(pRootOfTree) {
    // write code here
    let flag = true;
    // 头节点
    let head = null;
    // 指针节点（当前节点node的前一个节点）
    let pre = null;
    function postOrder(node) {
        if (node == null) {
            // 中序遍历，叶子节点为空则返回
            return head;
        }
        // 先中序遍历左节点，找到双线链表的头节点
        if (node.left) {
            postOrder(node.left);
        }
        if (flag == true) {
            // 若是第一个节点，头节点指向当前节点
            head = node;
            pre = head;
            flag = false;
        } else {
            // 若不是第一个节点，则pre的右节点指向当前节点
            pre.right = node;
            // 当前节点的左节点指向pre节点
            node.left = pre;
            // pre向后（右节点）指
            pre = node;
        }
        // 先中序遍历右节点
        if (node.right) {
            postOrder(node.right);
        }
        return head;
    }
    if (pRootOfTree == null) {
        return null;
    }
    let ans = postOrder(pRootOfTree);
    return ans;
}
module.exports = {
    Convert: Convert
};