给定数据结构：
const root = [
{
id: ‘1’,
children: [
{
id: ‘1-1’,
children: [{ id: ‘1-1-1’ }, { id: ‘1-1-2’ }],
},
{
id: ‘1-2’,
children: [{ id: ‘1-2-1’ }, { id: ‘1-2-2’ }],
},
],
},
{
id: ‘2’,
children: [
{
id: ‘2-1’,
children: [{ id: ‘2-1-1’ }, { id: ‘2-1-2’ }],
},
{
id: ‘2-2’,
children: [{ id: ‘2-2-1’ }, { id: ‘2-2-2’ }],
},
],
},
{
id: ‘3’,
children: [
{
id: ‘3-1’,
children: [{ id: ‘3-1-1’ }, { id: ‘3-1-2’ }],
},
{
id: ‘3-2’,
children: [{ id: ‘3-2-1’ }, { id: ‘3-2-2’ }],
},
],
},
];
const target = ‘2-2-2’;
DFS递归和非递归
深度优先搜索（depth first search），从图中也可以看出来，是从根节点开始，沿树的深度进行搜索，尽可能深的搜索分支。当节点所在的边都已经搜多过，则回溯到上一个节点，再搜索其余的边。
深度优先搜索采用栈结构，后进先出。
算法：
js 递归实现和非递归实现：
const depthFirstSearchWithRecursive = source => {
const result = []; // 存放结果的数组
// 递归方法
const dfs = data => {
// 遍历数组
data.forEach(element => {
// 将当前节点 id 存放进结果
result.push(element.id);
// 如果当前节点有子节点，则递归调用
if (element.children && element.children.length > 0) {
dfs(element.children);
}
});
};
// 开始搜索
dfs(source);
return result;
};
const depthFirstSearchWithoutRecursive = source => {
const result = []; // 存放结果的数组
// 当前栈内为全部数组
const stack = JSON.parse(JSON.stringify(source));
// 循环条件，栈不为空
while (stack.length !== 0) {
// 最上层节点出栈
const node = stack.shift();
// 存放节点
result.push(node.id);
// 如果该节点有子节点，将子节点存入栈中，继续下一次循环
const len = node.children && node.children.length;
for (let i = len - 1; i >= 0; i -= 1) {
stack.unshift(node.children[i]);
}
}
return result;
};
3. 广度优先搜索
广度优先搜索（breadth first search），从图中也可以看出来，是从根节点开始，沿树的宽度进行搜索，如果所有节点都被访问，则算法中止。
广度优先搜索采用队列的形式，先进先出。
js 实现：
const breadthFirstSearch = source => {
const result = []; // 存放结果的数组
// 当前队列为全部数据
const queue = JSON.parse(JSON.stringify(source));
// 循环条件，队列不为空
while (queue.length > 0) {
// 第一个节点出队列
const node = queue.shift();
// 存放结果数组
result.push(node.id);
// 当前节点有子节点则将子节点存入队列，继续下一次的循环
const len = node.children && node.children.length;
for (let i = 0; i < len; i += 1) {
queue.push(node.children[i]);
}
}
return result;
};