js创建线段树导致堆栈溢出怎么解?

五月花开
  • 1.3k

使用JavaScript构建一棵线段树,在构建过程中使用了递归,应该是这个原因使得调用栈溢出,不知道大家还有没有其他方法能够解决这个问题?

代码

class SegmentTree {
    constructor(arr, merge) {
        // 保存数组的拷贝
        this.data = arr.slice();
        this.tree = [];
        this.merge = merge;
        this._buildSegmentTree(0, 0, this.data.length - 1);
    }

    _buildSegmentTree(treeIndex, l, r) {
        // 递归退出条件
        if (l === r) {
            this.tree[treeIndex] = this.data[l];
            return;
        }
        // 构建子树
        let leftTreeIndex = this.leftChild(treeIndex);
        let rightTreeIndex = this.rightCild(treeIndex);
        let mid = (l + (l + r) / 2) | 0;
        this._buildSegmentTree(leftTreeIndex, l, mid);
        this._buildSegmentTree(rightTreeIndex, mid + 1, r);
        // 根据子节点创建父节点
        this.tree[treeIndex] = this.merge(this.tree[leftTreeIndex], this.tree[rightTreeIndex]);
    }

    leftChild(index) {
        return index * 2 + 1;
    }
    rightCild(index) {
        return index * 2 + 2;
    }
}


let arr = [1, 2, 3];
let segTree = new SegmentTree(arr, (a, b) => a + b);
console.log(segTree.tree);

错误截图

图片描述

回复
阅读 1.7k
2 个回答

判断条件写的有问题吧,没有及时停止递归

左右边界中间值计算出现了问题,这里应该是:

let mid = (l + (r - l) / 2) | 0;
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏