关于二叉树的关联关系

来源:11-2 对称二叉树-代码实操

MeSKiL

2019-09-18

class Tree {
    constructor(data) {
        let nodeList = [];
        let root;
        let list = data.map(item => {
            return new TreeNode(item)
        });
        for (let i = 0, len = list.length; i < len; i++) {
            let node = list[i];
            nodeList.push(node);
            if (list[2 * i + 1]) {
                node.left = list[2 * i + 1];
            }
            if (list[2 * i + 2]) {
                node.right = list[2 * i + 2];
            }
        }
        root = nodeList.shift();
        nodeList.length = 0;
        return root
    }
}

老师,我觉得子节点找父节点。然后再关联,虽然只要遍历一次,但是从逻辑上来讲太麻烦了,还要算层级还要算左右节点等等。
如果先把所有节点都创建以后,一个节点的左节点是他下标的2n+1,右节点是2n+2。比如list[2]的左节点是list[5],右节点是list[6]。
这样的话,只要2n+1存在就赋值成他的左节点,2n+2存在就赋值成他的右节点。
这样虽然会遍历两次数组,但是时间复杂度还是一样的。而且逻辑比较容易理解呀。还是说这样做有啥不好的地方嘛

写回答

1回答

快乐动起来呀

2019-09-25

 不好意思回复晚了,你这个逻辑没问题,只是你想下怎么从底层的节点向上找父节点的,你要知道树的节点只有两个信息左和右,通过这种关系来引用。所以下面的节点是找不到上面节点的,你想想看

0
0

JavaScript版 数据结构与算法

填补前端同学的算法短板,掌握面试中最常见的算法与数据结构

2467 学习 · 395 问题

查看课程