深度优先遍历与广度优先遍历

深度优先遍历

深度优先遍历就是当我们搜索一个树的分支时，遇到一个节点，我们会优先遍历它的子节点，直到最后根节点为止，最后再遍历兄弟节点，从兄弟子节点寻找它的子节点，直到搜索到最后结果，然后结束。

// 树形结构
const root = {
	name: "1",
	children: [
		{
			name: "2-1",
			children: [
				{
					name: "3-1",
					children: [
						{
							name: "4-2",
							children: null,
						},
						{
							name: "4-1",
							children: null,
						},
					],
				},
				{
					name: "3-2",
					children: null,
				},
			],
		},
		{
			name: "2-2",
			children: null,
		},
	],
}

// 深度优先遍历 递归
const deepDFS = (root, nodeList = []) => {
	if (root) {
		nodeList.push(root.name)
		root.children && root.children.forEach((v) => deepDFS(v, nodeList))
	}
	return nodeList
}

// 非递归
const deepDFS = (root: TreeNode): string[] => {
	// 存储遍历结果
	let nodeList: string[] = []
	// 存储需要处理的节点
	let stack: TreeNode[] = []
	if (root) {
		stack.push(root)
	}
	while (stack.length > 0) {
		let node = stack.pop()
		nodeList.push(node.name)
		if (node.children) {
			// 将子节点逆序压入栈，以便先遍历左子节点
			for (let i = node.children.length - 1; i >= 0; i--) {
				stack.push(node.children[i])
			}
		}
	}
	return nodeList
}

广度优先遍历

搜索树分支时，从根节点开始，当访问子节点时，先遍历找到兄弟节点，再寻找对应自己的子节点

广度优先遍历的主要思想是将一个树放到一个队列中，我们循环这个队列，判断该队列的长度是否大于 0，我们不断循环队列，shift 出队列操作，然后判断节点 children,循环 children,然后将子节点添加到队列中，一旦队列的长度为 0，那么就终止循环了。

// 广度优先遍历
const deepBFS = (root, nodeList = []) => {
	const queue = [root] // 循环判断队列的长度是否大于0
	while (queue.length > 0) {
		// 取出队列添加的节点
		const p = queue.shift()
		nodeList.push(p.name) // 根据节点是否含有children,如果有子节点则添加到队列中
		p.children && p.children.forEach((v) => queue.push(v))
	}
	return nodeList
}