二叉搜索树与双向链表

题目描述

示例

代码

代码1 中序遍历，将结果保存在数组中，通过数组构建双向链表

/*
二叉搜索树 采用中序遍历（左根右）
正好得到一个从小到大排好序的数组
通过数组在构建双向链表
*/
function Convert(pRootOfTree)
{
    if(!pRootOfTree) return null
    
    let result = [] // 中序遍历拿到的排好序的节点，通过这个节点构造双向链表
    // 开始中序遍历
    inOrder(pRootOfTree)
    
    // 开始拼接链表
    for(let i = 0; i < result.length-1; i++){
        result[i].right = result[i+1]
        result[i+1].left = result[i]
    }
    
    return result[0] // 返回头结点
    
    
    // 中序遍历 左根右
    function inOrder(pRootOfTree){
        // 出口
        if(!pRootOfTree) return;
        
        // 递归遍历
        inOrder(pRootOfTree.left) // 左
        result.push(pRootOfTree) // 根 直接把当前节点的引用保存到数组中，因为题目要求不构建新的节点，所以只能用原来的
        inOrder(pRootOfTree.right) // 右
    }
    
}

时间复杂度：O(N)，等于中序遍历的时间复杂度。 空间复杂度：O(N)，开辟了一个数组来存储结点。

代码2 中序遍历，遍历的途中直接修改指针指向（全局保存一个前驱节点）

/*
因为是二叉搜索树，采用中序遍历直接就是从小到大的结果
所以本题就采用中序遍历，
因为题目要求在原树上操作
所以在遍历的途中把指针给修改了

关键难点在于 如何记录 前一个节点

*/
function Convert(pRootOfTree)
{
    if(!pRootOfTree) return null
    
    let preNode = null // 递归的途中，记录上一个节点
    
    // 找到最左侧的节点，待会好返回
    // 返回的头结点，就是二叉搜索树最左侧的那个节点
    let head = pRootOfTree 
    while(head.left) {
        head = head.left
    }
    
    // 开始遍历，同时修改指针指向，将二叉搜索树转换为双向链表
    inOreder(pRootOfTree)
    
    // 转换完成，返回结果
    return head
    
    
    // 中序遍历（左根右）的过程中，将指针都修改完毕
    function inOreder(pRootOfTree){
        // 出口
        if(!pRootOfTree) return;
        
        inOreder(pRootOfTree.left) // 左
        
        //当前结点中需要进校的调整。
        pRootOfTree.left = preNode
        // 最左侧的节点第一次进来时，preNode尚未初始化，默认的为null，所以增加一个判断
        if(preNode) {
            preNode.right = pRootOfTree
        }
        
        preNode = pRootOfTree //更新preNode，指向当前结点，作为下一个结点的前驱。
        
        inOreder(pRootOfTree.right) // 右
    }
    
}

时间复杂度：O(N)，等于中序遍历的时间复杂度。 空间复杂度：O(N)。没有申请新的空间，但是递归调用栈占用了N的空间。

题目来源

JZ36 二叉搜索树与双向链表