二叉树的数据结构在js中可以如此表示:
const tree = {
value: 1,
left: {
value: 2,
left: {
value: 4,
left: {
value: 8
},
right: {
value: 9
}
},
right: {
value: 5
}
},
right: {
value: 3,
left: {
value: 6
},
right: {
value: 7
}
}
}
我们分别采用深度和广度遍历一遍：
深度优先
此处就使用前序遍历了
递归实现
function dfsRecursion(tree) {
let res = [];
function dfs(node){
if(node) {
res.push(node.value);
dfs(node.left);
dfs(node.right);
}
}
dfs(tree);
return res;
}
非递归实现
/**
* @param tree
* 非递归实现，需要自行实现“回溯”，可以使用栈来巧妙实现
* 将某个节点的右节点、左节点依次压倒栈中，会先消费该左节点，再次将其右子节点、左子节点压入栈...
*/
function dfsNonRecursion(tree) {
let arr = [];
let res = [];
arr.push(tree);
while (arr.length) {
const node = arr.pop();
res.push(node.value);
if (node.right) {
arr.push(node.right);
}
if (node.left) {
arr.push(node.left);
}
}
return res
}
广度优先
function bfs(tree) {
let res = [];
let arr = [];
arr.push(tree);
while(arr.length) {
const node = arr.shift();
res.push(node.value);
if(node.left) {
arr.push(node.left);
}
if(node.right) {
arr.push(node.right);
}
}
return res;
}
