When traversing a binary tree in front, middle, or post-order, we use a stack to simplify operations. This is because they are all recursive structures of DFS, which means processing from bottom to top. However, I always start writing code from the root node, so I need a stack, and the stack is first-in-first-out. This way, I can process the root node last.
Level-order traversal is BFS, from top to bottom. The root element that was enqueued first is also the one I want to process first. This is why DFS uses a stack and BFS uses a queue.
DFS algorithm flow and template
First, place the root node in the stack.
Remove the first node from the stack and check if it is the target. If all nodes are found, the search ends and the result is returned. Otherwise, add one of its unchecked direct child nodes to the stack.
Repeat step 2.
If there are no unchecked direct child nodes, add the parent node to the stack.
Repeat step 2.
Repeat step 4.
If the stack is empty, the entire graph has been checked—that is, there is no target to be found. The search ends and the result is returned: “Target not found.”
function dfs(root) {
if (满足特定条件）{
// Return results or exit search space }
for (const child of root.children) {
dfs(child)
}
}
```### BFS algorithm flow and template
1. First, place the root node in the queue.
1. Remove the first node from the queue and check if it is the target.
- If the target is found, the search ends and the result is returned.
- Otherwise, all of its direct children that have not yet been checked are added to the queue.
1. If the queue is empty, the entire graph has been searched—that is, there is no target to be found. The search ends and the result is "target not found."
1. Repeat step 2.
```javascript
function bfs(root) {
var que = [root]
while(que.length) {
var node = que.shift()
if (node 是我们要找到的) return node
node.left && que.push(node.left)
node.right && que.push(node.right)
}
}