Open wingmeng opened 5 years ago
上一期介绍了 队列和队列的模拟,这一期来看看队列的应用。
这是一道经典的面试题,要求不使用递归广度遍历下面的二叉树:
要求在控制台依次输出遍历结果:1, 2, 3, 4, 5, 6, 7, 8
测试数据:
{ "value": 1, "left": { "value": 2, "left": { "value": 4 } }, "right": { "value": 3, "left": { "value": 5, "left": { "value": 7 }, "right": { "value": 8 } }, "right": { "value": 6 } } }
思路:
广度遍历的特点是从根节点开始,沿着树的宽度一层一层进行遍历,直到所有节点都被遍历完为止,我们可以利用队列来实现这个算法。
核心思路是用一个队列来临时保存节点。遍历开始时先将根节点加入队列,然后从队列中取出第一个元素(此时是根节点),同时将该节点的子节点(如有)加入队列,以此循环操作,直至队列为空。参照下图示意(点击可查看大图):
上码:
function levelOrderTraversal(tree) { var queue = []; // 使用数组模拟队列 queue.push(tree); // 根节点入队列 while (queue.length !== 0) { tree = queue.shift(); // 取出队列第一个节点 console.log(tree.value); if (tree.left) { queue.push(tree.left); // 左子节点入队列 } if (tree.right) { queue.push(tree.right); // 右子节点入队列 } } }
上一期介绍了 队列和队列的模拟,这一期来看看队列的应用。
这是一道经典的面试题,要求不使用递归广度遍历下面的二叉树:
测试数据:
思路:
广度遍历的特点是从根节点开始,沿着树的宽度一层一层进行遍历,直到所有节点都被遍历完为止,我们可以利用队列来实现这个算法。
核心思路是用一个队列来临时保存节点。遍历开始时先将根节点加入队列,然后从队列中取出第一个元素(此时是根节点),同时将该节点的子节点(如有)加入队列,以此循环操作,直至队列为空。参照下图示意(点击可查看大图):
上码: