【数据结构与算法】102. 二叉树的层序遍历
Opened this issue · 1 comments
sayid760 commented
// 模拟树结构
// 节点对象
class Node {
constructor(data) {
this.root = this;
this.data = data;
this.left = null;
this.right = null;
}
}
// 二叉树
class BST {
constructor() {
this.root = null;
}
// 插入节点
insert(data) {
if (!data) return
let newNode = new Node(data);
let insertNode = (node, newNode) => {
if (newNode.data < node.data) {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode)
}
}
};
if (!this.root) {
this.root = newNode;
} else {
insertNode(this.root, newNode)
}
}
}
let datas = [3, 2, 15, null, null, 7, 20]
let bst = new BST();
datas.forEach(data => {
bst.insert(data)
})
方法一:深度优先搜索
var levelOrder = function (root) {
if (!root) return []
let res = []
dfs(root, 0, res)
return res
};
function dfs(root, level, res) {
if (root) {
if (!res[level]) res[level] = []
res[level].push(root.data)
dfs(root.left, level + 1, res)
dfs(root.right, level + 1, res)
}
}
// 方法二: 广度优先搜索
var levelOrder = function (root) {
if(!root) return []
console.log([root])
let queue = [root] // [Node {root: Node, data: 3, left: Node, right: Node}]
let res = []
while(queue.length>0){
let len = queue.length
let arr = []
while(len){
let node = queue.shift()
arr.push(node.data)
if(node.left) queue.push(node.left)
if(node.right) queue.push(node.right)
console.log(queue)
len--
}
res.push(arr)
}
return res
}
console.log(levelOrder(bst.root))
/* 输出
[
[3],
[2,15],
[7,20]
]
*/