Useful Information Note

根据顺序输出二叉树的每个节点的值

题目:根据顺序输出二叉树的每个节点的值。

这一题在算法中比较的基础,其实也没有什么难度。面试官的要求是需要使用时间复杂度为O(n)的方式进行输出。

根据顺序输出二叉树的每个节点的值

解题思路:

其实这里考察了一下队列的知识。下面我们来看一下队列的基本描述图:

队列的基本描述图

根据队列的思想,首先访问第一个节点,然后输出该节点的值,然后判断它是否具备子节点。如果具备将子节点放入队列,然后依次遍历队列,知道遍历到队列的最后一个。

代码:

var node7 = {
    num: 7,
    children: []
}; // 节点7
var node6 = {
    num: 6,
    children: []
};
var node5 = {
    num: 5,
    children: []
};
var node4 = {
    num: 4,
    children: []
};
var node3 = {
    num: 3,
    children: [node6, node7]
};
var node2 = {
    num: 2,
    children: [node4, node5]
};
var node1 = {
    num: 1,
    children: [node2, node3]
};

var queue = []; // 队列
queue.push(node1); // 现将第一个节点push进去
for (var i = 0; i < queue.length; i++) {
    var node = queue[i];
    console.log(node.num);
    if (node.children.length !== 0) { // 判断是否含有子节点
        for (var j = 0; j < node.children.length; j++) {
            queue.push(node.children[j]);
        }
    }
}


上一篇:找出数组中出现次数最的元素,并给出其出现过的位置
下一篇:将给定字符串逐个提取出()[]并输出