剑指offer - 二叉搜索树与双向链表

二叉搜索树与双向链表

http://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5

【二叉搜索树与双向链表】【2种解法（一次递归或递归+遍历）】

题目描述

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

解法 1: 一次递归（推荐）

二叉搜索树的性质是：左节点 < 当前节点 < 右节点。转换后的双向链表是有序的，这里采用中序递归遍历保证有序性。

设计的递归函数返回的是：已转换好的双向链表的尾结点，也就是当前节点的 left 指针应该指向的地方。递归函数的实现思路：

检查 left 是否为空，不为空，那么递归调用（传入左子树）
将 left 指针指向已转换好的双向链表的尾结点，并将尾节点的 right 指向当前节点
更新双向链表尾节点（变为当前节点），检查 right 是否为空，不为空，递归调用（传入右子树）
返回转换后的双向链表尾节点

代码实现如下。逻辑在__Convert()函数中，Convert()函数的目的是因为牛客网 oc 条件需要返回转换后链表的首节点。

// ac地址：https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
// 原文地址：https://xxoo521.com/2020-02-06-btree-link/

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
/**
 * @param {TreeNode} pRootOfTree
 * @return {TreeNode}
 */
function Convert(pRootOfTree) {
    if (!pRootOfTree) {
        return null;
    }
    __Convert(pRootOfTree, null);
    let node = pRootOfTree;
    while (node.left) {
        node = node.left;
    }
    return node;
}

/**
 * @param {TreeNode} pRootOfTree
 * @param {TreeNode} lastNodeInList
 * @return {TreeNode}
 */
function __Convert(pRootOfTree, lastNodeInList = null) {
    if (!pRootOfTree) {
        return null;
    }
    // step1:左子树
    if (pRootOfTree.left) {
        lastNodeInList = __Convert(pRootOfTree.left, lastNodeInList);
    }
    // step2:当前节点
    pRootOfTree.left = lastNodeInList;
    if (lastNodeInList) {
        lastNodeInList.right = pRootOfTree;
    }
    // step3:右子树
    lastNodeInList = pRootOfTree;
    if (pRootOfTree.right) {
        lastNodeInList = __Convert(pRootOfTree.right, lastNodeInList);
    }

    return lastNodeInList;
}

整个过程的要递归遍历一遍二叉树，时间复杂度是 O(N)，空间复杂度是 O(N)。

解法 2: 递归+数组

解法 2 的实现非常简单。流程如下：

中序遍历一遍二叉搜索树，将节点保存在一个数组中。
遍历数组，更改每个节点的 left 和 right
返回数组第一个元素

// ac地址：https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
// 原文地址：https://xxoo521.com/2020-02-06-btree-link/

/**
 * @param {TreeNode} pRootOfTree
 * @return {TreeNode}
 */
function Convert(pRootOfTree) {
    if (!pRootOfTree) {
        return null;
    }

    const nodes = [];
    midTravel(pRootOfTree, nodes);
    const num = nodes.length;
    for (let i = 0; i < num; ++i) {
        nodes[i].right = nodes[i + 1] || null;
        nodes[i].left = nodes[i - 1] || null;
    }
    return nodes[0];
}
/**
 * @param {TreeNode} node
 * @param {TreeNode[]} nodes
 */
function midTravel(node, nodes) {
    node.left && midTravel(node.left, nodes);
    nodes.push(node);
    node.right && midTravel(node.right, nodes);
}

时间复杂度是 O(N)，空间复杂度是 O(N)。相较于解法 1，多开辟了 O(N)的数组空间。但是整体思路更容易想到和实现。