树的遍历
Opened this issue · 0 comments
lovelmh13 commented
树具有子结构,一旦涉及子问题,考虑使用「递归」完成。
中序遍历
�如果出现顺序的数组,要组成一个二叉搜索树,那么用中序遍历。因为 BST 的中序遍历是升序的。
层次遍历
关键使用「队列」,从左到右,从上到下的便利
const BFS = function(root) {
if (!root) {
return []
}
let queue = [root]
const res = []
while (queue.length > 0) {
const node = queue.shift()
res.push(node.val)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
console.log(res)
return res
}
步骤:
- 创建一个队列。把 root 存进去
- 循环队列,把 node 出队列。存入结果
- 有左子树就把左子树压入队列
- 有右子树就把右子树压入队列