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

心谭博客

发布于 2020-04-21 10:43:17

5460

发布于 2020-04-21 10:43:17

文章被收录于专栏：YuanXinYuanXin

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

题目分析

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

题目要求循环双向链表，因此尾节点的 right 要指向首节点，首节点的 left 要指向尾节点。

解法 1: 递归+中序遍历

结合中序遍历，递归处理二叉树。初始化一个代表上一个节点的 pre 变量。递归中要做的就是：pre 的 right 指针指向当前节点 node，node 的 left 指向 pre，并且将 pre 更新为 node。

要注意的是，当递归到最下面的左节点时，pre 为空，要保留节点作为循环链表的 head。并在中序遍历结束后，处理头节点和尾节点的指针关系。

代码如下：

// ac地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
// 原文地址：https://xxoo521.com/2020-02-06-btree-link/

/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function(root) {
    if (!root) {
        return;
    }
    let head = null;
    let pre = head;
    inorder(root);
    // 完成中序遍历后，pre指向了最后一个节点
    // 将其闭合成环状结构
    head.left = pre;
    pre.right = head;
    return head;

    /**
     * @param {Node} node
     */
    function inorder(node) {
        if (!node) return;
        // 遍历左子树
        inorder(node.left, pre);

        // 处理当前节点
        if (!pre) {
            // 遍历到最左边节点，此时节点就是双向链表的head
            head = node;
        } else {
            pre.right = node;
        }
        node.left = pre;
        pre = node;

        // 遍历右子树
        inorder(node.right, pre);
    }
};

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

解法 2: 非递归+中序遍历

这里可以将递归转换为非递归的的中序遍历。转化思路是用栈来模拟递归调用的过程，其他的处理和解法 1 一样。

代码如下：

// ac地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
// 原文地址：https://xxoo521.com/2020-02-06-btree-link/

/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function(root) {
    if (!root) {
        return;
    }

    const stack = [];
    let node = root;
    let pre = null;
    let head = null;
    while (stack.length || node) {
        if (node) {
            stack.push(node);
            node = node.left;
        } else {
            const top = stack.pop();
            if (!pre) {
                head = top;
            } else {
                pre.right = top;
            }
            top.left = pre;
            pre = top;

            node = top.right;
        }
    }

    head.left = pre;
    pre.right = head;
    return head;
};

关于前序、中序和后序的非递归写法可以参考这篇文章：《二叉树前序、中序、后序遍历非递归写法的透彻解析》。这里不再多说。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-02-06，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法