剑指Offer——二叉搜索树与双向链表(JS实现)

题目描述

剑指Offer——二叉搜索树与双向链表(JS实现)

解题思路

  • 使用二叉树的中序遍历,将每一个节点存到一个数组中
  • 使用for循环改变每个节点的left,right指针域

实现代码

var treeToDoublyList = function (root) {
    const temp = [];
    function dfs(root) {
        if (!root) return null;

        dfs(root.left);
        temp.push(root)
        dfs(root.right);
        return null;
    }
    dfs(root);
    const len = temp.length;
    for (let i = 0; i < temp.length; i++) {
        if (i !== 0) {
            temp[i].left = temp[i - 1];
        } else {
            temp[i].left = temp[len-1];
        }
        if (i !== len - 1) {
            temp[i].right = temp[i + 1];
        } else {
            temp[i].right = temp[0];
        }
    }
    return temp[0];
};

作者:Always_positive
链接:https://juejin.cn/post/6948663629428293646
来源:稀土掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
上一篇:剑指offer系列之二十五:二叉搜索树与双向链表


下一篇:8个CSS图表数据制作实例